The Alon-Tarsi number of a planar graph minus a matching

DOI10.1016/J.JCTB.2020.02.005MaRDI QIDQ2200936zbMATH OpenOpenAlexWikidataFDO

Authors Jarosław Grytczuk, Xuding Zhu

Publication date 24 September 2020

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

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

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: This paper proves that every planar graph $G$ contains a matching $M$ such that the Alon-Tarsi number of $G-M$ is at most $4$. As a consequence, $G-M$ is $4$-paintable, and hence $G$ itself is $1$-defective $4$-paintable. This improves a result of Cushing and Kierstead [Planar Graphs are 1-relaxed, 4-choosable, {em European Journal of Combinatorics} 31(2010),1385-1397], who proved that every planar graph is $1$-defective $4$-choosable.

Recommendations

• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• The Alon-Tarsi number of planar graphs
• The Alon-Tarsi number of \(K_5\)-minor-free graphs
• The Alon-Tarsi number of two kinds of planar graphs
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs

Cites work

• scientific article; zbMATH DE number 1250667 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 890665 (Why is no real title available?)
• A refinement of choosability of graphs
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Defective 3-paintability of planar graphs
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar graph is 5-choosable
• List Improper Colourings of Planar Graphs
• List colourings of planar graphs
• Locally planar graphs are 2-defective 4-paintable
• Mr. Paint and Mrs. Correct
• On \(t\)-common list-colorings
• On two generalizations of the Alon-Tarsi polynomial method
• On-line list colouring of graphs
• Planar graphs are 1-relaxed, 4-choosable
• The Alon-Tarsi number of planar graphs

Cited in

(18)

• Graph polynomials and group coloring of graphs
• On the Alon-Tarsi number of semi-strong product of graphs
• Decomposing planar graphs into graphs with degree restrictions
• Toroidal graphs without \(K_5^-\) and 6-cycles
• A note on Alon-Tarsi number of Halin graphs
• Graph polynomials and paintability of plane graphs
• Decomposing graphs of nonnegative characteristic into subgraphs with degree restrictions
• The Alon–Tarsi number of planar graphs revisited
• The Alon-Tarsi number of planar graphs without cycles of lengths 4 and \(l\)
• A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
• The Alon-Tarsi number of planar graphs
• Schnyder woods and Alon-Tarsi number of planar graphs
• Weak (2, 3)-decomposition of planar graphs
• The Alon-Tarsi number of \(K_5\)-minor-free graphs
• Every planar graph is 1-defective \((9,2)\)-paintable
• The polynomial method for list-colouring extendability of outerplanar graphs
• Decomposition of planar graphs with forbidden configurations
• The Alon-Tarsi number of cupolarotundas and gyroelongated rotunda

This page was built for publication: The Alon-Tarsi number of a planar graph minus a matching

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