The polynomial method for list-colouring extendability of outerplanar graphs

DOI10.26493/1855-3974.2398.7D5MaRDI QIDQ5020296zbMATH OpenOpenAlexFDO

Authors Przemysław Gordinowicz, Paweł Twardowski

Publication date 5 January 2022

Published in Ars Mathematica Contemporanea (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.07679

zbMATH Keywords

Alon-Tarsi numberlist colouringouterplanar graphpaintability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31)

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.

Recommendations

• On list-coloring extendable outerplanar graphs
• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• On list-coloring outerplanar graphs
• Hypergraph extension of the Alon-Tarsi list coloring theorem
• scientific article; zbMATH DE number 2188336

Cites work

• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Every planar graph is 5-choosable
• Five-list-coloring graphs on surfaces. I. Two lists of size two in planar graphs
• Five-list-coloring graphs on surfaces. III: One list of size one and one list of size two
• Mr. Paint and Mrs. Correct
• On list-coloring extendable outerplanar graphs
• The Alon-Tarsi number of a planar graph minus a matching
• The Alon-Tarsi number of planar graphs

Cited in

(3)

• On list-coloring extendable outerplanar graphs
• Application of polynomial method to on-line list colouring of graphs
• The polynomial method for three-path extendability of list colourings of planar graphs

This page was built for publication: The polynomial method for list-colouring extendability of outerplanar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5020296)