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

Jarosław Grytczuk , Xuding Zhu


This paper proves that every planar graph Gcontains 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 (2010) [5], who proved that every planar graph is 1-defective 4-choosable
Author Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Xuding Zhu
Xuding Zhu,,
Journal seriesJournal of Combinatorial Theory Series B, [Journal of Combinatorial Theory. Series B], ISSN 0095-8956, e-ISSN 1096-0902
Issue year2020
Keywords in Polishkolorowanie grafów
Keywords in EnglishPlanar graph, List colouring, On-line list colouring, Alon-Tarsi number
ASJC Classification1703 Computational Theory and Mathematics; 2607 Discrete Mathematics and Combinatorics; 2614 Theoretical Computer Science
Languageen angielski
Score (nominal)140
Score sourcejournalList
ScoreMinisterial score = 140.0, 09-07-2020, ArticleFromJournal
Publication indicators Scopus Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 1.678; WoS Impact Factor: 2018 = 0.892 (2) - 2018=1.158 (5)
Citation count*
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?