Total colourings of planar graphs with large girth
type: Item
instance of: scholarly article
title: Total colourings of planar graphs with large girth
zbMATH Open document ID: 0886.05065
published in: European Journal of Combinatorics
publication date: 1998-04-07T00:00:00Z
review text: The total chromatic number \(X''=X''(G)\) of a graph \(G\) is the smallest number of colours that suffice to colour the vertices and edges of \(G\) so that no two adjacent or incident elements have the same colour. It is clear that \(X''\geq \Delta+1\), and \textit{M. Behzad} [Doctoral Thesis, Michigan State University, 1965] and \textit{V. G. Vizing} [Usp. Mat. Nauk 23, No. 6(144), 117-134 (1968; Zbl 0177.52301 and Zbl 0192.60502)] conjectured that \(X''\leq \Delta+2\), for every graph \(G\) with maximum degree \(\Delta\). For planar graphs with \(\Delta \geq 9\) the conjecture was verified by \textit{O. V. Borodin} [J. Reine Angew. Math. 394, 180-195 (1989; Zbl 0653.05029)]. In this paper the girth is involved into the the play. Recall that the girth of a graph is the length of its shortest cycle. Theorem: Let \(G\) be a planar graph with maximum degree \(\Delta\) and girth \(g\). Then \(X''(G)=\Delta+1\) in each of the following cases: (a) \(\Delta \geq 11\); (b) \(\Delta \geq 7\) and \(g\geq 4\); (c) \(\Delta \geq 5\) and \(g\geq 5\); (d) \(\Delta\geq 4\) and \(g\geq 6\); (e) \(\Delta\geq 3\) and \(g\geq 10\). The cases (a) and (b) were proved by the same authors in previous papers. In the present paper the rest cases (c), (d) and (e) are proved. The results (c), (d) and (e) hold also for graphs in the projective plane, torus, and Klein bottle. The papers brings also a survey of previous results concerning the topic.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1117436
zbMATH Keywords: total chromatic number
zbMATH Keywords: girth
zbMATH Keywords: planar graphs
author: Oleg V. Borodin
author: Alexandr Kostochka
author: Douglas R. Woodall
reviewed by: Stanislav Jendroľ
MaRDI profile type: Publication
full work available at URL: eujc.1997.0152
OpenAlex ID: W1976755379
DOI: 10.1006/EUJC.1997.0152
description: scientific article; zbMATH DE number 1117436