The Alon-Tarsi number of planar graphs

DOI10.1016/J.JCTB.2018.06.004zbMATH Open1402.05051arXiv1711.10817OpenAlexW2963961768MaRDI QIDQ1633764FDOQ1633764

Authors: Xuding Zhu 

Publication date: 20 December 2018

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

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.

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

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

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)

Cites Work

• Mr. Paint and Mrs. Correct
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• Colorings and orientations of graphs
• On-line list colouring of graphs
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• On two generalizations of the Alon-Tarsi polynomial method

Cited In (23)

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

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)