2010/10/14 by P. A. Petrosyan, Petros A. Petrosyan, Arman Yu. Torosyan +6
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM
paper · pdf · doi:10.48550/arxiv.1010.2989
23 pages, 1 figure
arxiv created 2010/10/14 · openalex publication_date 2010/10/14 · arxiv updated 2010/10/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A total coloring of a graph G is a coloring of its vertices and edges such that no adjacent vertices, edges, and no incident vertices and edges obtain the same color. 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 the vertex v in G. In this paper we investigate some properties of interval total colorings. We also determine exact values of the least and the greatest possible number of colors in such colorings for some classes of graphs.