A result on the total colouring of powers of cycles
type: Item
instance of: scholarly article
title: A result on the total colouring of powers of cycles
zbMATH Open document ID: 1124.05031
author: C. N. Campos
author: Célia P. de Mello
published in: Discrete Applied Mathematics
publication date: 2007-04-13T00:00:00Z
review text: The authors prove the following results: 1. Let \(G=C_n^k\), \(n\equiv0\pmod {k+1}\). Then \(\chi_T(G)\leq\Delta(G)+2\). 2. The graph \(G=C_n^k\), \(n\equiv r\pmod{k+1}\), with \(n\) even and \(r\neq0\), has a \((\Delta(G)+2)\)-total colouring. The authors conjecture: Let \(G=C_n^k\), with \(2\leq k<\lfloor \frac n2\rfloor\). Then \[ \chi_T(G)=\begin{cases} \Delta(G)+2&\text{if }k>\frac n3 -1\text{ and }n\text{ odd,}\\ \Delta(G)+1&\text{otherwise.}\end{cases} \]
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5142431
zbMATH Keywords: total colouring
zbMATH Keywords: total colouring conjecture
zbMATH Keywords: total chromatic number
zbMATH Keywords: powers of cycles
reviewed by: Chunhui Lai
MaRDI profile type: Publication
full work available at URL: j.dam.2006.08.010
OpenAlex ID: W2009349978
cites work: The Colour Numbers of Complete Graphs
cites work: Coloração Total do C²n
cites work: Total-chromatic number and chromatic index of dually chordal graphs
cites work: On planarity and colorability of circulant graphs
cites work: Total colouring regular bipartite graphs is NP-hard
cites work: Determining the total colouring number is NP-hard
cites work: Total colourings of graphs
DOI: 10.1016/J.DAM.2006.08.010
description: scientific article; zbMATH DE number 5142431