Uniquely total colorable graphs
type: Item
instance of: scholarly article
title: Uniquely total colorable graphs
zbMATH Open document ID: 0897.05038
DOI: 10.1007/BF03353009
published in: Graphs and Combinatorics
publication date: 1998-10-25T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1106813
zbMATH Keywords: total coloring
zbMATH Keywords: total chromatic number
author: S. Akbari
author: Mehdi Behzad
author: Hossein Hajiabolhassan
author: E. S. Mahmoodian
reviewed by: Mirosław Truszczyński
MaRDI profile type: Publication
cites work: Q4858958
cites work: Q5564134
cites work: Q4187840
cites work: Q3852212
cites work: Q3097395
cites work: On uniquely colorable planar graphs
cites work: ON THE CHROMATIC INDEX OF A GRAPH, III: UNIQUELY EDGE-COLOURABLE GRAPHS
cites work: Distinct representatives of subsets
cites work: Uniquely Line Colorable Graphs
cites work: Q4858979
cites work: The size of uniquely colorable graphs
cites work: Q3699709
description: scientific article; zbMATH DE number 1106813