The polynomial method for list-colouring extendability of outerplanar graphs

2019/12/16 by Przemysław Gordinowicz, Gordinowicz, Przemysław, Paweł Twardowski +1
Computer Science · Mathematics · #05C10 #05C15 #05C31 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05C10 #msc:05C15 #msc:05C31

paper · pdf · doi:10.48550/arxiv.1912.07679

arxiv created 2020/08/07 · arxiv updated 2020/08/11

Abstract

We restate theorems of Hutchinson on list-colouring extendability for outerplanar graphs in terms of non-vanishing monomials in a graph polynomial, which yields an Alon-Tarsi equivalent for her work. This allows to simplify her proofs as well as obtain more general results.

Related

• The polynomial method for 3-path extendability of list colourings of planar graphs
• Generalized list colouring of graphs
• An efficient implementation and a strengthening of Alon-Tarsi list coloring method
• Extension from Precoloured Sets of Edges
• A list analog of Vizing's Theorem for simple graphs with triangles but no other odd cycles