INTERVAL NON-TOTAL COLORABLE GRAPHS

Abstract

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,\ldots,t$ such that all colors are used, and the edges incident to each vertex $v$ together with $v$ are colored by $d_G(v)+1$ consecutive colors, where $d_G(v)$ is the degree of a vertex $v$ in $G$. In this paper we describe some methods for constructing of graphs that have no interval total coloring.