Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable

DOI10.1007/s40840-019-00819-4zbMath1437.05077OpenAlexW2965948659MaRDI QIDQ1988563

Jian-Bo Lv, Jie Liu

Publication date: 23 April 2020

Published in: Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s40840-019-00819-4

zbMATH Keywords

planar graphdischarging methodimproper coloring

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Related Items

Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable, The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles, Unnamed Item, Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests, Partitioning planar graphs without 4-cycles and 6-cycles into a linear forest and a forest

Cites Work

• Unnamed Item
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• 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
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• Near-colorings: non-colorable graphs and NP-completeness
• 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
• Improper choosability of graphs and maximum average degree