Planar graphs without adjacent cycles of length at most seven are 3-colorable

DOI10.1016/J.DISC.2009.08.010MaRDI QIDQ1045158zbMATH OpenOpenAlexFDO

Authors Oleg V. Borodin, Mickaël Montassier, André Raspaud

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

the 3-color problem

Mathematics Subject Classification ID

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

Recommendations

• On 3-colorability of planar graphs without adjacent short cycles
• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• On 3-colorable planar graphs without short cycles
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable

Cites work

• A 3-color theorem on plane graphs without 5-circuits
• A note on the three color problem
• A relaxation of Havel's 3-color problem
• A sufficient condition for planar graphs to be 3-colorable
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• 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 1109403 (Why is no real title available?)
• scientific article; zbMATH DE number 2097035 (Why is no real title available?)
• On a conjecture of B. Grünbaum
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Some counterexamples associated with the three-color problem
• Some simplified NP-complete graph problems
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

Cited in

(18)

• Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• A step towards the strong version of Havel's three color conjecture
• Planar graphs without adjacent cycles of length at most five are (2, 0, 0)-colorable
• Planar graphs without cycles of length from 4 to 7 and intersecting triangles are DP-3-colorable
• Every planar graph without adjacent cycles of length at most 8 is 3-choosable
• Note on 3-choosability of planar graphs with maximum degree 4
• Planar graphs without triangles adjacent to cycles of length from 3 to 9 are 3-colorable
• Facially-constrained colorings of plane graphs: a survey
• Short proofs of coloring theorems on planar graphs
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings
• Distance constraints on short cycles for 3-colorability of planar graphs
• A toughness condition for a spanning tree with bounded total excesses
• scientific article; zbMATH DE number 6746684 (Why is no real title available?)
• Planar graphs without triangles adjacent to cycles of length from 4 to 7 are 3-colorable
• The independence ratio of 4-cycle-free planar graphs
• Planar graphs without adjacent cycles of length at most five are (1,1,0)-colorable
• On 3-colorability of planar graphs without adjacent short cycles

This page was built for publication: Planar graphs without adjacent cycles of length at most seven are 3-colorable

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