On Interval Total Colorings of Trees

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 T (T ≠ K1) is a tree and Δ(T) + 2 ≤ t ≤ M(T) then T has an interval total t-coloring, where Δ(T) is the maximum degree of vertices in T and M(T) is a parameter which can be effectively found for any T.