Kaul-Mudrock Conjecture on the Unlabeled List Color Function
Donner proved in 1992 that the list color function equals the chromatic polynomial once is large. Kaul and Mudrock asked whether the analogue holds for Hanlon's unlabeled chromatic polynomial, and could not settle even the edgeless graph, which they posed as a conjecture. The conjecture is true, and it implies that a disconnected graph satisfies the unlabeled analogue of Donner's result whenever all of its components do.
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Argument
- Field
- Graph coloring
- Posed by
- Hemanshu Kaul, Jeffrey A. Mudrock
- Year posed
- 2024
- Years open
- 2y
- Solved
- 2026-07-18
- Model
- ChatGPT 5.5 Pro
- Vendor
- OpenAI
- Collaborators
- Hemanshu Kaul, Jeffrey A. Mudrock, Armin Straub, W. T. Gowers
- Verification
- Site-confirmed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
As part of an experiment, Gowers asked ChatGPT 5.5 Pro to find an open combinatorics problem it considered approachable and try to solve it. The model picked this conjecture unprompted and produced an affirmative proof, which Gowers passed to the authors and they confirmed correct. The authors had reached the same theorem independently by a shifting argument, so the model does not hold priority, but its proof is genuinely different (a shadow inequality in the style of the local LYM inequality) and appears in the appendix. Its output also revealed the general form of Corollary 1.6, which the authors had previously established only for complete graphs. Asked to settle the underlying question for all graphs, the model could not.
Verification
The authors state that they checked the AI-produced proof and found it correct, and they include a cleaned-up version of it in Appendix A. arXiv preprint; not yet peer-reviewed.
Source
arXiv:2607.16810 - The unlabeled list color function of disconnected graphs