Three coloring via triangle counting

MaRDI QIDQ6072056zbMATH OpenFDO

Authors Zachary Hamaker, Vincent Vatter

Publication date 29 November 2023

Full work available at URL https://arxiv.org/abs/2203.08136, http://ajc.maths.uq.edu.au/pdf/87/ajc_v87_p352.pdf

zbMATH Keywords

Ore's conjecturethree coloring conjecture

Mathematics Subject Classification ID

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

Recommendations

• Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles
• Three-colourability of planar graphs with no 5- or triangular \(\{3,6\}\)-cycles
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Planar graphs without 4, 6, 8-cycles are 3-colorable
• Plane graphs without cycles of length 4, 6, 7 or 8 are 3-colorable

Cites work

• 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 1109403 (Why is no real title available?)
• Ore's conjecture for k=4 and Grötzsch's theorem
• Ore's conjecture on color-critical graphs is almost true
• Planar graphs without cycles of length from 4 to 7 are 3-colorable
• Short proofs of coloring theorems on planar graphs
• Steinberg's conjecture is false
• Structural properties of plane graphs without adjacent triangles and an application to 3-colorings

Cited in

(2)

• Making triangles colorful
• Degeneracy of toroidal graphs without special cycles

This page was built for publication: Three coloring via triangle counting

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