Asymptotic online coloring of the graph C5+C_5^+

Let C5+C_5^+ be the graph obtained from the 5-cycle C5C_5 by adding the edge indicated in the paper, and let f(w,G)f(w,G) 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 ww. Asymptotic coloring conjecture.

f(w,C5+)=(54+o(1))w.f(w,C_5^+)=\left(\frac{5}{4}+o(1)\right)w.

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

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.