Asymptotic online coloring of the graph
Asymptotic online coloring of the graph
Let be the graph obtained from the 5-cycle by adding the edge indicated in the paper, and let denote the maximum number of colors that an adversary can force a deterministic online coloring algorithm to use when the clique number of the token graph is at most . Asymptotic coloring conjecture.
This is presented as an approachable open problem concerning the asymptotic behavior of the online coloring parameter for the remaining minimally non-online-perfect graphs; the paper does not establish the claimed asymptotic.
Sources & referencesView supporting material
Primary source
Kevin G. Milans and Michael C. Wigal, “Online coloring a token graph”, arXiv:1712.08699 (2017).
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.