The polynomial method for 3-path extendability of list colourings of planar graphs

2023/05/24 by Przemysław Gordinowicz, Gordinowicz, Przemysław, Paweł Twardowski +1
Computer Science · Engineering · #05C10 #05C15 #05C31 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2305.15509

openalex publication_date 2023/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We restate Thomassen's theorem of 3-extendability, an extension of the famous planar 5-choosability theorem, in terms of graph polynomials. This yields an Alon--Tarsi equivalent of 3-extendability.

Related

• The polynomial method for list-colouring extendability of outerplanar graphs
• An efficient implementation and a strengthening of Alon-Tarsi list coloring method
• A polynomial 3-colorability algorithm with automatic generation of NO 3-colorability (i.e. Co-NP) short proofs
• Schnyder woods and Alon-Tarsi number of planar graphs
• Multiple list colouring of planar graphs