Counterexamples disprove the conjecture that every K4-minor-free graph has a crumby coloring, with the smallest connected one having 18 vertices and a 2-connected one having 40 vertices.
The chromatic number of the square of subcubic planar graphs
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Wegner conjectured in 1977 that the square of every planar graph with maximum degree at most $3$ is $7$-colorable. We prove this conjecture using the discharging method and computational techniques to verify reducible configurations.
citation-role summary
background 1
citation-polarity summary
fields
math.CO 2roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Subcubic $K_4$-minor-free graphs without crumby colorings
Counterexamples disprove the conjecture that every K4-minor-free graph has a crumby coloring, with the smallest connected one having 18 vertices and a 2-connected one having 40 vertices.
- Coloring, List Coloring, and Painting Squares of Graphs (and other related problems)