The list color function threshold conjecture for complete bipartite graphs

Let K2,nK_{2,n} be the complete bipartite graph with parts of sizes 22 and nn, and let τ(G)\tau(G) denote the list color function threshold of a graph GG.

List color threshold conjecture.

τ(K2,n)=Θ(n)as n.\tau(K_{2,n}) = \Theta(\sqrt{n}) \quad\text{as } n \to \infty.

A lower bound of order n\sqrt{n} is known, while this conjecture asserts a matching upper bound and therefore determines the asymptotic growth of the threshold.

Sources & referencesView supporting material

Primary source

Hemanshu Kaul, Akash Kumar, Andrew Liu, Jeffrey A. Mudrock, Patrick Rewers, Paul Shin, Michael Scott Tanahara and Khue To, “Bounding the List Color Function Threshold from Above”, arXiv:2207.04831 (2022).

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.