EUVIMEDEUVIMED entdecken
Crossref

Graph Choosability via SAT: Beyond the Nullstellensatz

Markus Kirchweger, Tomáš Peitl, David Seka, Stefan Szeider

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →