Back
The Alon-Tarsi number of a planar graph minus a matching
Authors:
- Jarosław Grytczuk,
- Xuding Zhu
Abstract
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
- Record ID
- WUT20a54b0ede8a4f59a01fadc8fe074360
- Author
- Journal series
- Journal of Combinatorial Theory Series B, ISSN 0095-8956, e-ISSN 1096-0902
- Issue year
- 2020
- Vol
- 145
- Pages
- 511-520
- Publication size in sheets
- 0.50
- Keywords in Polish
- kolorowanie grafów
- Keywords in English
- Planar graph, List colouring, On-line list colouring, Alon-Tarsi number
- ASJC Classification
- ; ;
- Abstract in Polish
- W pracy dowodzimy, że każdy graf planarny G zawiera skojarzenie M takie, że liczba Alona-Tarsi′ego grafu G-M wynosi co najwyżej 4. W konsekwencji, graf G-M jest 4-malowalny, a więc G jest również 4-malowalny z defektem 1.To poprawia wynik Cushinga i Kiersteada, którzy udowodnili, że 4-wybieralność grafu planarnego z defektem 1.
- DOI
- DOI:10.1016/j.jctb.2020.02.005 Opening in a new tab
- URL
- https://www.sciencedirect.com/science/article/pii/S0095895620300095?via%3Dihub Opening in a new tab
- Language
- eng (en) English
- Score (nominal)
- 140
- Score source
- journalList
- Score
- = 140.0, 09-05-2022, ArticleFromJournal
- Publication indicators
- = 6; = 0; : 2018 = 1.678; : 2020 (2 years) = 1.317 - 2020 (5 years) =1.313
Share
- Uniform Resource Identifier
- https://repo.pw.edu.pl/info/article/WUT20a54b0ede8a4f59a01fadc8fe074360/
- URN
urn:pw-repo:WUT20a54b0ede8a4f59a01fadc8fe074360
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or PerishOpening in a new tab system.