Exponential 3-arboral coloring conjecture for toroidal graphs
Exponential 3-arboral coloring conjecture for toroidal graphs
Let be a graph embeddable in the torus. An arboreal 3-coloring of is a coloring with three colors such that each color class induces a forest. Exponential 3-arboral coloring conjecture. There exists an edge such that 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 , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.