
doi: 10.1007/bf03353009
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.
Coloring of graphs and hypergraphs, total coloring, total chromatic number
Coloring of graphs and hypergraphs, total coloring, total chromatic number
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
