Total coloring of planar graphs without adjacent short cycles
type: Item
instance of: scholarly article
title: Total coloring of planar graphs without adjacent short cycles
zbMATH Open document ID: 1367.05081
author: Yan Gu
author: Weili Wu
author: Bin Liu
author: Xin Zhang
author: Huijuan Wang
author: Hongwei Gao
published in: Journal of Combinatorial Optimization
publication date: 2017-03-03T00:00:00Z
review text: As well known, a total \(k\)-coloring of a graph \(G\) is a map \(c:V(G)\cup E(G)\rightarrow \{1,\ldots,k\}\) for which two adjacent or incident elements of \(V(G)\cup E(G)\) receive a different value, called color. The total chromatic number \(\chi^{\prime\prime}(G)\) is then the minimum integer \(k\) for which there exists a total \(k\)-coloring. A natural lower bound for this invariant is \(\Delta(G)+1\leq \chi^{\prime\prime}(G)\) where \(\Delta(G)\) represents the maximum degree of \(G\). Two cycles are adjacent if they share at least one edge. The authors show in this work that the total chromatic number of planar graphs without short adjacent cycles and big enough maximum degree equals to the above mentioned lower bound. More precisely, if \(\Delta(G)\geq 8\) and there are no adjacent cycles of length at most seven, then \(\chi^{\prime\prime}(G)=\Delta(G)+1\).
reviewed by: Iztok Peterin
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 6691097
zbMATH Keywords: total coloring
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
full work available at URL: s10878-015-9954-y
OpenAlex ID: W2175029141
cites work: Edge and total coloring of interval graphs
cites work: Q3097395
cites work: Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable
cites work: The total chromatic number of any multigraph with maximum degree five is at most seven
cites work: Total-Coloring of Plane Graphs with Maximum Degree Nine
cites work: Total colorings and list total colorings of planar graphs without intersecting 4-cycles
cites work: Total colouring regular bipartite graphs is NP-hard
cites work: Total coloring of planar graphs of maximum degree eight
cites work: Determining the total colouring number is NP-hard
cites work: On total 9-coloring planar graphs of maximum degree seven
cites work: Total colorings of planar graphs with maximum degree at least 8
cites work: The \(r\)-acyclic chromatic number of planar graphs
cites work: Total coloring of planar graphs with maximum degree 8
cites work: Minimum total coloring of planar graph
cites work: Q5463528
cites work: List-edge and list-total colorings of graphs embedded on hyperbolic surfaces
cites work: Total colourings of graphs
DOI: 10.1007/S10878-015-9954-Y
description: scientific article; zbMATH DE number 6691097