Planar Graphs Have Exponentially Many 3-Arboricities
Ararat Harutyunyan, Bojan Mohar · SIAM Journal on Discrete Mathematics · 2012
It is well known that every planar or projective planar graph can be 3-colored so that each color class induces a forest. This bound is sharp. In this paper, we show that there are in fact exponentially many 3-colorings of this kind for any (projective) planar graph. The same result holds in the setting of 3-list-colorings.