New answers tagged planar-graphs
2
This result is included in Ore's book The Four-Colour Problem (see Theorem 7.4.3).
I saw a paper that states this as a folklore result and cites Ore. Interestingly, the book gives a different proof for (ii)$\implies$(i). It seems that at that time, it wasn't known that the mapping $f\longmapsto f^*$ is a bijection.
Sorry to disappoint; but that's the best I ...
13
I can prove that no 4-regular graphs are 3-acyclic colorable.
Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting to either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as ...
Top 50 recent answers are included
