Two conjectures on uniquely totally colorable graphs
type: Item
instance of: scholarly article
title: Two conjectures on uniquely totally colorable graphs
zbMATH Open document ID: 1018.05025
DOI: 10.1016/S0012-365X(02)00797-5
published in: Discrete Mathematics
publication date: 2003-06-09T00:00:00Z
review text: 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\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1924754
zbMATH Keywords: total coloring
zbMATH Keywords: uniquely total colorable graph
author: S. Akbari
MaRDI profile type: Publication
Wikidata QID: Q56389090
cites work: Uniquely total colorable graphs
cites work: Q5422499
cites work: On uniquely colorable planar graphs
cites work: Hamiltonian Cycles and Uniquely Edge Colourable Graphs
full work available at URL: s0012-365x(02)00797-5
OpenAlex ID: W1968469640
DBLP publication ID: journals/dm/Akbari03
description: scientific article; zbMATH DE number 1924754