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

DOI10.1016/J.JCTB.2020.02.005zbMATH Open1448.05050arXiv1811.12012OpenAlexW3009314871WikidataQ112881845 ScholiaQ112881845MaRDI QIDQ2200936FDOQ2200936

Authors: Jarosław Grytczuk, Xuding Zhu 

Publication date: 24 September 2020

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

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.

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

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

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)

Cites Work

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

Cited In (18)

• Toroidal graphs without \(K_5^-\) and 6-cycles
• The polynomial method for list-colouring extendability of outerplanar graphs
• Every planar graph is 1-defective \((9,2)\)-paintable
• Graph polynomials and paintability of plane graphs
• The Alon–Tarsi number of planar graphs revisited
• The Alon-Tarsi number of planar graphs
• Graph polynomials and group coloring of graphs
• Decomposing planar graphs into graphs with degree restrictions
• A note on Alon-Tarsi number of Halin graphs
• 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
• Weak (2, 3)-decomposition of planar graphs
• A \((2, 1)\)-decomposition of planar graphs without intersecting 3-cycles and adjacent \(4^-\)-cycles
• Decomposing graphs of nonnegative characteristic into subgraphs with degree restrictions
• The Alon-Tarsi number of \(K_5\)-minor-free 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)