Equitable list colouring

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph, $n=|V|\ge1$, and $\Delta(G)=\max_{v\in V}d_G(v)$. A $k$-list assignment supplies a set $L(v)$ of exactly $k$ distinct colour names to each vertex. Lists need not agree, and their union may contain more than $k$ colours. A proper list colouring chooses $f(v)\in L(v)$ so that adjacent vertices receive different colours.

Such a colouring is equitable in the list-colouring sense if \[ |\{v:f(v)=a\}|\le\left\lceil\frac nk\right\rceil \quad\text{for every colour }a. \] The conjecture asserts that for every integer $k\ge\Delta(G)+1$ and every $k$-list assignment, a proper colouring with this bound exists.

Only the upper size bound is imposed on each colour class. A matching lower bound is inappropriate for arbitrary lists, since some colour names may occur at only one vertex. In particular, the assertion does not require the use of a common palette of exactly $k$ colours. The lists are chosen adversarially and independently at the vertices; the conclusion must hold for each assignment. Ordinary equitable colourability, where every list is the same, is thus only a special case of the problem.

Short English statement

Can every graph be properly coloured from arbitrary lists of size at least one more than its maximum degree, without any colour being used too often?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000033 (AMR-029-0033), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Equitable list colouring. Original source indexed by AMR-029-0033. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Equitable list colouring. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Equitable_list_colouring.