Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable

DOI10.1007/S00373-023-02713-0MaRDI QIDQ6081925zbMATH OpenFDO

Authors Xiangwen Li, Jie Liu, Jianbo Lv

Publication date 29 November 2023

Published in Graphs and Combinatorics (Search for Journal in Brave)

zbMATH Keywords

planar graphcoloringdefective coloring

Mathematics Subject Classification ID

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

Recommendations

• Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• Planar graphs without cycles of length 4 or 7 are \((2, 0, 0)\)-colorable

Cites work

• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• A relaxation of the Bordeaux conjecture
• A relaxation of the strong Bordeaux Conjecture
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• Defective 2-colorings of sparse graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph with cycles of length neither 4 nor 5 is \((1,1,0)\)-colorable
• Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
• Improper choosability of graphs and maximum average degree
• Improper coloring of graphs on surfaces
• List improper colorings of planar graphs with prescribed girth
• Near-colorings: non-colorable graphs and NP-completeness
• On \((3,1)^*\)-coloring of plane graphs
• Partitioning planar graphs without 4-cycles and 5-cycles into bounded degree forests
• Planar graphs with girth at least 5 are \((3, 5)\)-colorable
• Planar graphs without cycles of length 4 or 5 are (3,0,0)-colorable
• Planar graphs without cycles of length 4 or 5 are \((2, 0, 0)\)-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Steinberg's conjecture is false

Cited in

(3)

• Every signed planar graph without cycles of length from 4 to 8 is 3-colorable
• Planar graphs without 4- and 6-cycles are \(( 3 , 4 )\)-colorable
• Planar graphs without 3-cycles adjacent to cycles of length 3 or 5 are \((3, 1)\)-colorable

This page was built for publication: Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6081925)