Planar graphs with girth at least 5 are \((3, 5)\)-colorable

DOI10.1016/j.disc.2014.11.012zbMath1305.05072OpenAlexW2162181764MaRDI QIDQ488297

Ilkyoo Choi, Andre Raspaud

Publication date: 23 January 2015

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

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

zbMATH Keywords

planar graphsdischarging methodimproper coloring

Mathematics Subject Classification ID

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

Related Items (15)

A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable ⋮ Every planar graph with girth at least 5 is \((1,9)\)-colorable ⋮ Defective 2-colorings of planar graphs without 4-cycles and 5-cycles ⋮ Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs ⋮ Colouring planar graphs with bounded monochromatic components ⋮ Partitioning sparse graphs into an independent set and a graph with bounded size components ⋮ An (F1,F4)‐partition of graphs with low genus and girth at least 6 ⋮ Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable ⋮ Unnamed Item ⋮ Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable ⋮ Splitting a planar graph of girth 5 into two forests with trees of small diameter ⋮ Near-colorings: non-colorable graphs and NP-completeness ⋮ On the vertex partition of planar graphs into forests with bounded degree ⋮ Planar graphs with girth at least 5 are \((3, 4)\)-colorable ⋮ An \((F_3,F_5)\)-partition of planar graphs with girth at least 5

Cites Work

• On 1-improper 2-coloring of sparse graphs
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Near-colorings: non-colorable graphs and NP-completeness
• Defective 2-colorings of sparse graphs
• 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
• Unnamed Item

This page was built for publication: Planar graphs with girth at least 5 are \((3, 5)\)-colorable