Uniquely total colorable graphs (Q1376076): Difference between revisions

A total coloring of a graph is an assignment of colors to the vertices and edges of the graph so that no two adjacent edges have the same color, no two adjacent vertices have the same color and no vertex and an incident edge have the same color. The minimum number of colors needed by a total coloring is called the total chromatic number and is denoted \(\chi'' (G)\). A graph is uniquely total colorable (UTC) if it admits exactly one (up to a renaming of colors) total coloring with \(\chi'' (G)\) colors. The paper is concerned with the following conjecture: if a graph is uniquely total colorable, then it is an empty graph, a path, or a cycle with \(3k\) vertices. Several results supporting this conjecture are given. It is proved, for instance, that every UTC graph that is not an edge satisfies \(\chi'' (G)= \Delta (G)+1\). In another theorem, it is shown that the vertices of degree \(\Delta\) form a vertex cover of a graph that is a UTC.