Unlabelled list-colouring counts for edgeless graphs

If one chooses one element from each of n sets of size k, must at least binomial(k+n−1,n) different multisets be obtainable? This is the edgeless-graph case of the unlabeled list-coloring problem.

Why it matters and what counts as progress

Why it matters: The edgeless case isolates the multiset combinatorics underlying unlabeled list coloring before graph adjacency adds constraints.

What counts as progress: Prove the multiset lower bound, determine equality or extend it to graphs with edges and disconnected graphs.

How the problem developed

1985 · Partial result [1]
Phil Hanlon Developed the chromatic polynomial theory for unlabelled graphs, a predecessor to unlabelled list-colouring counts.
9 Sept 2024 · Definition [2]
Christine Kaul and John Mudrock Introduced the unlabelled list-colouring function and developed results analogous to the labelled list-colouring setting.
18 Jul 2026 · Theorem [3]
Christine Kaul, John Mudrock and Einar Steingrímsson Straub Proved the unlabelled list-colouring count formula for edgeless graphs and extended the result to disconnected graphs whose components each satisfy the stated condition.

AI contribution

The unlabeled list color function of disconnected graphs

Hemanshu Kaul, Jeffrey A. Mudrock, Armin Straub

Appendix A proves that choosing one element from each of n sets of size k yields at least binomial(k+n−1,n) distinct multisets, using a multiset-shadow coupling. This establishes the edgeless-graph case of the unlabeled list-color conjecture.

AI involvementAI-autonomous

ImportanceModest

Technical verificationFormal (human)

Human understandingFull