Point Arboricity Critical Graphs Exist
Béla Bollobás, Frank Harary · Journal of the London Mathematical Society · 1975
The point arboricity of a graph is the minimum number of colours assignable to the points so that no cycle is monochromatic. A graph is called k-critical if it is connected and the removal of any edge reduces the point arboricity from k to k − 1. The existence of k-critical graphs of odd order only was established by Kronk and Mitchem. We construct here k-critical graphs of every possible even order.