Three-coloring planar graphs without short cycles

DOI10.1016/J.IPL.2006.08.009MaRDI QIDQ845915zbMATH OpenOpenAlexFDO

Authors Min Chen, André Raspaud, Weifan Wang

Publication date 29 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2006.08.009

zbMATH Keywords

coloringplanar graphwithout odd cycles

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On 3-colorable planar graphs without short cycles
• On 3-colorability of planar graphs without adjacent short cycles
• On 3-colorable planar graphs without prescribed cycles
• On 3-colorable planar graphs without cycles of four lengths
• Total coloring of planar graphs without short cycles
• Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
• On the 3-colorability of planar graphs without 4-, 7- and 9-cycles
• The \((3, 3)\)-colorability of planar graphs without 4-cycles and 5-cycles
• Planar graph colorings without short monochromatic cycles
• Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles

Cites work

• A note on 3-choosability of planar graphs without certain cycles
• A note on the three color problem
• scientific article; zbMATH DE number 434910 (Why is no real title available?)
• scientific article; zbMATH DE number 54790 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• On 3-colorable plane graphs without 5- and 7-cycles
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

Cited in

(9)

• On the 3-colorability of planar graphs without 4-, 7- and 9-cycles
• A step towards the strong version of Havel's three color conjecture
• On 3-colorable planar graphs without cycles of four lengths
• Short proofs of coloring theorems on planar graphs
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
• Characterization of Cycle Obstruction Sets for Improper Coloring Planar Graphs
• Planar graph colorings without short monochromatic cycles
• On 3-colorable planar graphs without short cycles

This page was built for publication: Three-coloring planar graphs without short cycles

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