Some counterexamples associated with the three-color problem

DOI10.1016/0095-8956(80)90051-9zbMath0434.05033MaRDI 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

05C10: Planar graphs; geometric and topological aspects of graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

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