Graph Choosability via SAT: Beyond the Nullstellensatz
Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14269-14277
DOI: 10.1609/aaai.v40i17.38441 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Markus Kirchweger und 3 weiteren Autor:innen.
Abstract (Originalsprache)
List coloring extends graph coloring by assigning each vertex a list of allowed colors. A graph is k-choosable if it can be properly colored for any choice of lists with k colors each. Deciding k-choosability is π²ₚ-complete, bipartite graphs have unbounded list chromatic number, and planar graphs (famously 4-colorable) are all 5-choosable but not all 4-choosable. To search for graphs of given choosability, we extend SAT Modulo Symmetries (SMS) with custom propagators for list coloring pruning techniques and propose a quantified Boolean (QBF) encoding for choosability. We employ a hybrid approach: pen-and-paper reasoning to optimize our formulas followed by automated case distinction by QBF solvers and SMS. Our methods yield two significant results: (1) a 27-vertex planar graph that is 4-choosable yet cannot be proven so using the combinatorial Nullstellensatz widely applied in previous work (we show this is a smallest graph with that property), and (2) the smallest graph exhibiting a gap between chromatic and list chromatic numbers for chromatic number 3.
Zitieren
APA
Kirchweger, M., Peitl, T., Seka, D., & Szeider, S. (2026). Graph Choosability via SAT: Beyond the Nullstellensatz. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14269-14277. https://doi.org/10.1609/aaai.v40i17.38441
Vancouver
Kirchweger M, Peitl T, Seka D, Szeider S. Graph Choosability via SAT: Beyond the Nullstellensatz. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14269-14277. doi:10.1609/aaai.v40i17.38441
BibTeX
@article{Kirchweger2026,
author = {Kirchweger, Markus and Peitl, Tomáš and Seka, David and Szeider, Stefan},
title = {Graph Choosability via SAT: Beyond the Nullstellensatz},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
year = {2026},
volume = {40},
number = {17},
pages = {14269--14277},
doi = {10.1609/aaai.v40i17.38441}
}
EUVIMED