Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs

DOI10.1137/16M1106882zbMath1388.05061arXiv1806.06212WikidataQ129731519 ScholiaQ129731519MaRDI QIDQ4564884

Ilkyoo Choi, Chun-Hung Liu, Sang-il Oum

Publication date: 7 June 2018

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

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

zbMATH Keywords

graph coloringplanar graphsobstruction setsimproper coloringdefective coloring

Mathematics Subject Classification ID

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

Related Items (2)

Graph partitions under average degree constraint ⋮ Vertex partitions of \((C_3, C_4, C_6)\)-free planar graphs

Cites Work

• Unnamed Item
• Steinberg's conjecture is false
• On 1-improper 2-coloring of sparse graphs
• 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
• Planar graphs without cycles of length 4, 7, 8, or 9 are 3-choosable
• Three-coloring planar graphs without short cycles
• On 3-colorable plane graphs without 5- and 7-cycles
• Planar graphs without cycles of length 4, 5, 8, or 9 are 3-choosable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The four-colour theorem
• List improper colorings of planar graphs with prescribed girth
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• A note on 3-choosability of planar graphs without certain cycles
• Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions
• (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
• A Complexity Dichotomy for the Coloring of Sparse Graphs
• Improper coloring of graphs on surfaces
• Improper choosability of graphs and maximum average degree

This page was built for publication: Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs