New answers tagged

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