Interval Total Colorings of Certain Graphs - Petrosyan, Petros A. (Mathematical Problems of Computer Science, 2021)
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 with each vertex v together with v are colored by (dG(v) + 1) consecutive colors, where dG(v) is the degree of the vertex v in G. It is proved that complete graphs, complete bipartite graphs and n-dimensional cubes have interval total colorings and bounds are found for the possible number of colors in such colorings.