Every planar graph with girth at least 5 is \((1,9)\)-colorable

DOI10.1016/j.disc.2022.112818zbMath1486.05096MaRDI QIDQ2124609

Jian-Bo Lv, Xiangwen Li, Jie Liu

Publication date: 11 April 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2022.112818

zbMATH Keywords

planar graph; coloring; discharging method; improper coloring

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

An \((F_3,F_5)\)-partition of planar graphs with girth at least 5

Cites Work

• Unnamed Item
• Planar graphs with girth at least 5 are \((3, 5)\)-colorable
• Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• Planar graphs without 5-cycles and intersecting triangles are \((1, 1, 0)\)-colorable
• List improper colorings of planar graphs with prescribed girth
• Near-colorings: non-colorable graphs and NP-completeness
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
• Defective 2-colorings of sparse graphs
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• List Improper Colourings of Planar Graphs
• Improper choosability of graphs and maximum average degree