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

DOI10.1016/J.DISC.2014.11.012MaRDI QIDQ488297zbMATH OpenOpenAlexFDO

Authors Ilkyoo Choi, André 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)

Recommendations

• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Every planar graph with girth at least 5 is (1,9)-colorable
• A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
• (1,k)-Coloring of Graphs with Girth at Least Five on a Surface
• Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable

Cites work

• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• Defective 2-colorings of sparse graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Improper choosability of graphs and maximum average degree
• List Improper Colourings of Planar Graphs
• Near-colorings: non-colorable graphs and NP-completeness
• On 1-improper 2-coloring of sparse graphs
• Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most \(k\)
• Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1

Cited in

(23)

• Distinguishing colorings of 3-connected planar graphs with five colors
• Every planar graph without 4-cycles and 5-cycles is \((2, 6)\)-colorable
• An \((F_3,F_5)\)-partition of planar graphs with girth at least 5
• Near-colorings: non-colorable graphs and NP-completeness
• A sufficient condition for planar graphs with girth 5 to be \((1,7)\)-colorable
• Splitting a planar graph of girth 5 into two forests with trees of small diameter
• Partitioning planar graph of girth 5 into two forests with maximum degree 4.
• Planar graphs without 4- and 6-cycles are \(( 3 , 4 )\)-colorable
• A sufficient condition for planar graphs with girth 5 to be \((1,6)\)-colorable
• Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
• An (F1,F4)‐partition of graphs with low genus and girth at least 6
• On the vertex partition of planar graphs into forests with bounded degree
• Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
• Planar graphs with girth at least 5 are \((3, 4)\)-colorable
• Every planar graph without 4-cycles and 5-cycles is (3,3)-colorable
• Partitioning planar graphs with girth at least 6 into bounded size components
• Every planar graph with girth at least 5 is (1,9)-colorable
• Planar graphs of girth at least five are square \((\delta + 2)\)-choosable
• Fractional coloring of planar graphs of girth five
• scientific article; zbMATH DE number 6746684 (Why is no real title available?)
• Planar graphs without cycles of length 3, 4, and 6 are (3, 3)-colorable
• Colouring planar graphs with bounded monochromatic components
• Partitioning sparse graphs into an independent set and a graph with bounded size components

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

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