The Alon-Tarsi number of planar graphs

DOI10.1016/J.JCTB.2018.06.004MaRDI QIDQ1633764zbMATH OpenOpenAlexFDO

Authors Xuding Zhu

Publication date 20 December 2018

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

planar graphlist colouringon-line list colouringAlon-Tarsi number

Mathematics Subject Classification ID

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

Abstract: This paper proves that the Alon-Tarsi number of any planar graph is at most $5$, which gives an alternate proof of the $5$-choosability as well as the $5$-paintability of planar graphs.

Recommendations

• The Alon-Tarsi number of two kinds of planar graphs
• The Alon-Tarsi number of a planar graph minus a matching
• The Alcuin Number of a Graph
• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• On almost-planar graphs
• On the crossing number of almost planar graphs
• On the Crossing Number of Almost Planar Graphs
• An algebraic characterization of planar graphs
• Cyclomatic numbers of planar graphs
• Counting planar graphs and related families of graphs

Cites work

• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• Colorings and orientations of graphs
• Every planar graph is 5-choosable
• Mr. Paint and Mrs. Correct
• On two generalizations of the Alon-Tarsi polynomial method
• On-line list colouring of graphs

Cited in

(23)

• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• Graph polynomials and group coloring of graphs
• On the Alon-Tarsi number of semi-strong product of graphs
• Toroidal graphs without \(K_5^-\) and 6-cycles
• Combinatorial Nullstellensatz and DP-coloring of graphs
• A note on Alon-Tarsi number of Halin graphs
• Graph polynomials and paintability of plane graphs
• The Alon-Tarsi number of a toroidal grid
• The Alon-Tarsi number of two kinds of planar graphs
• Weak degeneracy of planar graphs and locally planar graphs
• Alon-Tarsi numbers of direct products
• The Alon–Tarsi number of planar graphs revisited
• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• Decomposition of toroidal graphs without some subgraphs
• On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
• The Alon-Tarsi number of a planar graph minus a matching
• Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz
• Schnyder woods and Alon-Tarsi number of planar graphs
• A strengthening and an efficient implementation of Alon-Tarsi list coloring method
• The Alon-Tarsi number of \(K_5\)-minor-free graphs
• Relation between the correspondence chromatic number and the Alon-Tarsi number
• The polynomial method for list-colouring extendability of outerplanar graphs
• The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda

This page was built for publication: The Alon-Tarsi number of planar graphs

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