Upper Bounds for the Maximum Span in Interval Total Colorings of Graphs
Petros A. Petrosyan, Nerses A. Khachatryan · Mathematical Problems of Computer Science · 2011
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 a connected graph G with n vertices admits an interval total t-coloring, then t≤2n-1. Furthermore, we show that if G is a connected r-regular graph with n vertices which has an interval total t-coloring and n≥2r+2, then this upper bound can be improved to 2n i 3. We also give some other upper bounds for the maximum span in interval total colorings of graphs.