Two conjectures on uniquely totally colorable graphs
An element of a graph \(G\) is a vertex or an edge of \(G\). Two elements are associated if they are two adjacent vertices, or two edges having a common endvertex, or one is an edge and the other is an endvertex of that edge. A total coloring of \(G\) is a partition of the elements of \(G\) into disjoint color classes such that no two associated elements belong to the same class. Uniquely total colorable graphs have exactly one total coloring (except for permutations) with a smallest possible number of color classes. The author continues an investigation on uniquely total colorable graphs in [\textit{S. Akbari, M. Behzad} and \textit{E. S. Mahmoodian}, Graphs Comb. 13, 305-314 (1997; Zbl 0897.05038)]. The results are: (1) The maximum degree of a uniquely total colorable graph with \(n\) vertices is at most \((n/2) + 1\). (2) If in a (unique) total coloring of a uniquely total colorable graph some color does not appear at any vertex, then the graph is regular of degree at least \(n/2\).
scientific article; zbMATH DE number 1924754