Interval Total Colorings of Graphs with a Spanning Star

Abstract

An interval total t-coloring of a graph G is a total coloring of G with colors 1, 2,…t such that at least one vertex or edge of G is colored by I, i = 1, 2,…t, and the edges incident to each vertex v together with v are colored by dG(v) + 1 consecutive colors, where dG(v) is the degree of a vertex v in G. In this paper we prove that if G = (V;E) is a graph containing the vertex u with dG(u) = |V| – 1, k(G) = maxv2V (v≠u)dG(v) < |V| – 1 and G admits an interval total t-coloring then t ≤ |V| + 2k(G). We also show that this upper bound is sharp. Further we determine all possible values of t for which the wheels have an interval total t-coloring.