We restate Thomassen's theorem of 3-extendability (Thomassen, Journal of Combinatorial Theory Series B, 97, 571–583), an extension of the famous planar 5-choosability theorem, in terms of graph polynomials. This yields an Alon–Tarsi equivalent of 3-extendability.

Open Research

Data Availability Statement

The authors have nothing to report.

References

1C. Thomassen, “Every Planar Graph Is 5-Choosable,” Journal of Combinatorial Theory Series B 62 (1994): 180–181.
10.1006/jctb.1994.1062
Web of Science® Google Scholar
2C. Thomassen, “Exponentially Many 5-List-Colorings of Planar Graphs,” Journal of Combinatorial Theory Series B 97 (2007): 571–583.
10.1016/j.jctb.2006.09.002
Web of Science® Google Scholar
3X. Zhu, “Alon-Tarsi Number of Planar Graphs,” Journal of Combinatorial Theory Series B 134 (2019): 354–358.
10.1016/j.jctb.2018.06.004
Web of Science® Google Scholar
4N. Alon, “Combinatorial Nullstellensatz,” Combinatorics, Probability, and Computing 8 (1999): 7–29.
10.1017/S0963548398003411
Web of Science® Google Scholar
5N. Alon and M. Tarsi, “Colorings and Orientations of Graphs,” Combinatorica 12 (1992): 125–134.
10.1007/BF01204715
Web of Science® Google Scholar
6U. Schautz, “Mr. Paint and Mrs. Correct,” Electronic Journal of Combinatorics 16 (2009): R77:1–18.
Google Scholar
7J. Grytczuk and X. Zhu, “The Alon-Tarsi Number of a Planar Graph Minus a Matching,” Journal of Combinatorial Theory Series B 145 (2020): 511–520.
10.1016/j.jctb.2020.02.005
Web of Science® Google Scholar
8X. Zhu and R. Balakrishnan, Combinatorial Nullstellensatz: With Applications to Graph Colouring (Chapman and Hall/CRC Press, 2021).
10.1201/9781003138679
Google Scholar
9D. B. West, Introduction to Graph Theory (Prentice Hall, 2001), 2nd edition.
Google Scholar
10P. Gordinowicz and P. Twardowski, “The Polynomial Method for List-Colouring Extendability of Outerplanar Graphs,” Ars Mathematica Contemporanea 21 (2021): #P2.08.
10.26493/1855-3974.2398.7d5
Google Scholar
11T. Böhme, B. Mohar, and M. Stiebitz, “Dirac's Map-Color Theorem for Choosability,” Journal of Graph Theory 32 (1999): 327–339.
10.1002/(SICI)1097-0118(199912)32:4<327::AID-JGT2>3.0.CO;2-B
Web of Science® Google Scholar
12J. P. Hutchinson, “On List-Coloring Extendable Outerplanar Graphs,” Ars Mathematica Contemporanea 5 (2012): 175–188.
10.26493/1855-3974.179.189
Google Scholar
13L. Postle and R. Thomas, “Five-List-Coloring Graphs on Surfaces I. Two Lists of Size Two in Planar Graphs,” Journal of Combinatorial Theory Series B 111 (2015): 234–241.
10.1016/j.jctb.2014.08.003
Google Scholar
14L. Postle and R. Thomas, “Five-List-Coloring Graphs on Surfaces II. A Linear Bound for Critical Graphs in a Disk,” Journal of Combinatorial Theory Series B 119 (2016): 42–65.
10.1016/j.jctb.2015.12.005
Google Scholar
15L. Postle and R. Thomas, “Five-List-Coloring Graphs on Surfaces III. One List of Size One and One List of Size Two,” Journal of Combinatorial Theory Series B 128 (2018): 1–16.
10.1016/j.jctb.2017.06.004
Google Scholar

Volume109, Issue2

June 2025

Pages 237-254

The Polynomial Method for Three-Path Extendability of List Colourings of Planar Graphs

ABSTRACT

Open Research

Data Availability Statement

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

The Polynomial Method for Three-Path Extendability of List Colourings of Planar Graphs

ABSTRACT

Open Research

Data Availability Statement

References

References

Related

Information