Exponential 3-arboral coloring conjecture for toroidal graphs

Let GG be a graph embeddable in the torus. An arboreal 3-coloring of GG is a coloring with three colors such that each color class induces a forest. Exponential 3-arboral coloring conjecture. There exists an edge eE(G)e\in E(G) such that GeG-e has exponentially many arboreal 3-colorings. The paper observes that every toroidal graph has an edge whose deletion leaves a graph of vertex-arboricity at most 33, and conjectures that one such deletion always yields exponentially many 3-arboral colorings. The conjecture is presented without a resolution in the paper.

Sources & referencesView supporting material

Primary source

Ararat Harutyunyan and Bojan Mohar, “Planar graphs have exponentially many 3-arboricities”, arXiv:1110.4900 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.