Choice Number of k-Chromatic Graphs of Bounded Order

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A graph is $q$-choosable if for every assignment of a list of $q$ available colors to each vertex, it has a proper coloring using an available color at each vertex. Its choice number $\operatorname{ch}(G)$ is the least such $q$. Let $\chi(G)$ denote chromatic number and $\alpha(G)$ the maximum size of an independent vertex set. Write $K_{m*k}$ for the complete $k$-partite graph with every part of size $m$.

Statement recorded in the supplied source.

For all integers $m,k\ge1$, does every $k$-chromatic graph $G$ on at most $mk$ vertices satisfy $\operatorname{ch}(G)\le\operatorname{ch}(K_{m*k})$? The source also asks the refinement: for every $n\ge k\ge1$, does there exist a complete $k$-partite graph $G_{n,k}$ on $n$ vertices with $\alpha(G_{n,k})=\lceil n/k\rceil$ such that \[\operatorname{ch}(G)\le\operatorname{ch}(G_{n,k})\] for every $k$-chromatic graph $G$ on at most $n$ vertices? In particular, the $m=4$ case asks for the bound $\operatorname{ch}(G)\le\lceil(3k-1)/2\rceil$ when $|V(G)|\le4k$. [S2]

Short English statement

Among graphs of bounded order and fixed chromatic number, does a suitably balanced complete multipartite graph maximize the choice number?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3241 (OPG-44879). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Choice Number of k-Chromatic Graphs of Bounded Order, original node 44879, statement and mathematical discussion. https://www.openproblemgarden.org/op/choice_number_of_k_chromatic_graphs_of_bounded_order.