Some counterexamples associated with the three-color problem

DOI10.1016/0095-8956(80)90051-9zbMath0434.05033OpenAlexW2080252381MaRDI QIDQ1139601

V. A. Aksionov, Leonid S. Mel'nikov

Publication date: 1980

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0095-8956(80)90051-9

zbMATH Keywords

non-3-colorable planar graphs

Mathematics Subject Classification ID

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

Related Items (max. 100)

Irreducible graphs in the Grünbaum-Havel 3-colour problem ⋮ A step towards the strong version of Havel's three color conjecture ⋮ 3-choosability of planar graphs with \((\leqslant 4)\)-cycles far apart ⋮ A relaxation of Havel's 3-color problem ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ Choosability of toroidal graphs without short cycles ⋮ Three-coloring triangle-free graphs on surfaces. V: Coloring planar graphs with distant anomalies ⋮ Planar 4-critical graphs with four triangles ⋮ A note on the three color problem ⋮ Decomposing a planar graph of girth 5 into an independent set and a forest ⋮ Adapted list coloring of planar graphs ⋮ Note on 3-choosability of planar graphs with maximum degree 4 ⋮ Planar graphs without adjacent cycles of length at most seven are 3-colorable ⋮ A counterexample to the conjecture of Aksionov and Mel'nikov on non-3- colorable planar graphs

Cites Work

• Grötzsch's theorem on 3-colorings
• On a conjecture of B. Grünbaum
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Some counterexamples associated with the three-color problem