Existence of a subforest preserving game chromatic number

Let FF be a forest, and let \FF\F'\subseteq F be a subforest. Write Δ(F)\Delta(F') for its maximum degree and χg(F)\chi_{\rm g}(F') for its game chromatic number.

Subforest preservation conjecture. There exists a subforest FFF'\subseteq F such that

Δ(F)χg(F)\Delta(F')\leq \chi_{\rm g}(F)

and

χg(F)=χg(F).\chi_{\rm g}(F')=\chi_{\rm g}(F).

The conjecture would reduce the study of the game chromatic number of forests to subforests whose maximum degree is bounded by the original game chromatic number. It is stated in the conclusions as an open question; the preceding results provide classification criteria in some degree-restricted cases but do not establish the claim in general.

Sources & referencesView supporting material

Primary source

Charles Dunn, Victor Larsen, Kira Lindke, Troy Retter and Dustin Toci, “The game chromatic number of trees and forests”, arXiv:1410.5223 (2014).

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.