Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
type: Item
instance of: scholarly article
title: Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
zbMATH Open document ID: 1462.05115
author: Xiangwen Li
author: Qin Shen
author: Fanyu Tian
published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series
publication date: 2021-04-27T00:00:00Z
review text: A graph \(G\) is \((d_1, d_2, \ldots, d_k)\)-colorable if the vertex set of \(G\) can be partitioned into subsets \(V_1, V_2, \ldots , V_k\) such that the subgraph \(G[V_i ]\) induced by \(V_i\) has maximum degree at most \(d_i\) for \(i \in \{ 1, \ldots , k\}\). \textit{C. Zhang} et al. [Discrete Math. 339, No. 12, 3032--3042 (2016; Zbl 1343.05054)] asked whether every planar graph without adjacent cycles of length at most 5 is (1, 0, 0)-colorable. \textit{M. Chen} et al. [ibid. 339, No. 2, 886--905 (2016; Zbl 1327.05073)] approximated this conjecture by proving that every planar graph without cycles of length 4 and 5 is (2, 0, 0)-colorable. The authors improve this result by proving that every planar graph without adjacent cycles of length at most five is (2, 0, 0)-colorable.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 7339965
zbMATH Keywords: coloring
zbMATH Keywords: planar graphs
zbMATH Keywords: improper coloring
reviewed by: Eckhard Steffen
MaRDI profile type: Publication
full work available at URL: s40840-020-01004-8
OpenAlex ID: W3082304758
cites work: Planar graphs with neither 5-cycles nor close 3-cycles are 3-colorable
cites work: A sufficient condition for planar graphs to be 3-colorable
cites work: Planar graphs without cycles of length from 4 to 7 are 3-colorable
cites work: Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
cites work: Planar graphs without adjacent cycles of length at most seven are 3-colorable
cites work: Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
cites work: Steinberg's conjecture is false
cites work: A relaxation of the Bordeaux conjecture
cites work: Q3139765
cites work: Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable
DOI: 10.1007/S40840-020-01004-8
Recommended article: Planar graphs without adjacent cycles of length at most five are \((1,1,0)\)-colorable
Recommended article: Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
Recommended article: Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
Recommended article: Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable
Recommended article: Every planar graph without 5-cycles and \(K_4^-\) and adjacent 4-cycles is \((2, 0, 0)\)-colorable
Recommended article: 2-distance coloring of planar graphs without adjacent 5-cycles
Recommended article: Planar graphs without cycles of length 4 or 7 are (2, 0, 0)-colorable
Recommended article: 1-planar graphs without 4-cycles or 5-cycles are 5-colorable
Recommended article: Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
Recommended article: 不含3圈和4圈的1-平面图是5-可染的
description: scientific article; zbMATH DE number 7339965