Vertex partitions of (C₃, C₄, C₆)-free planar graphs

DOI10.1016/J.DISC.2019.07.002MaRDI QIDQ2324512zbMATH OpenOpenAlexFDO

Authors François Dross, Pascal Ochem

Publication date 11 September 2019

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.08710

zbMATH Keywords

improper coloringsplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: A graph is $(k_1,k_2)$-colorable if its vertex set can be partitioned into a graph with maximum degree at most $k_1$ and and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.

Recommendations

• Planar graphs with cycles of length neither 4 nor 6 are \((2,0,0)\)-colorable
• Planar graphs without cycles of length 4 or 7 are (2, 0, 0)-colorable
• Planar graphs without 4-cycles and close triangles are \((2,0,0)\)-colorable
• Planar graphs without 4-cycle or chordal-6-cycle are (3, 0, 0)-colorable
• Every planar graph without cycles of length 4 or 9 is \((1, 1, 0)\)-colorable

Cites work

• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
• Defective 2-colorings of sparse graphs
• Improper coloring of sparse graphs with a given girth. I: \((0,1)\)-colorings of triangle-free graphs
• Near-colorings: non-colorable graphs and NP-completeness

Cited in

(4)

• A Catlin-type theorem for graph partitioning avoiding prescribed subgraphs
• Near-colorings: non-colorable graphs and NP-completeness
• Planar graphs without 4- and 6-cycles are \(( 3 , 4 )\)-colorable
• Planar graphs without cycles of length 3, 4, and 6 are (3, 3)-colorable

This page was built for publication: Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs

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