Article
| Title: | The Alon-Tarsi number of $K_{3,3}$-minor-free graphs (English) |
| Author: | Xu, Leyou |
| Author: | Zhou, Bo |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 76 |
| Issue: | 3 |
| Year: | 2026 |
| Pages: | 737-745 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| Summary: | Well-known Wagner's theorem states that a graph is a planar graph if and only if it is $K_5$-minor-free and $K_{3,3}$-minor-free. Denote by ${\rm AT}(G)$ the Alon-Tarsi number of a graph $G$. Let $G$ be a $K_{3,3}$-minor-free graph. We show that ${\rm AT}(G)\le 5$, ${\rm AT}(G-M)\le 4$ for some matching $M$, and ${\rm AT}(G-E(F))\le 3$ for some forest $F$, extending the results on the Alon-Tarsi number of planar graphs due to Zhu and his co-authors. (English) |
| Keyword: | Alon-Tarsi number |
| Keyword: | $K_{3,3}$-minor-free graph |
| Keyword: | planar graph |
| MSC: | 05C15 |
| DOI: | 10.21136/CMJ.2026.0215-24 |
| . | |
| Date available: | 2026-09-11T13:09:57Z |
| Last updated: | 2026-09-14 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/153725 |
| . | |
| Reference: | [1] Abe, T., Kim, S.-J., Ozeki, K.: The Alon-Tarsi number of $K_5$-minor-free graphs.Discrete Math. 345 (2022), Article ID 112764, 7 pages. Zbl 1482.05094, MR 4357324, 10.1016/j.disc.2021.112764 |
| Reference: | [2] Alon, N., Tarsi, M.: Colorings and orientations of graphs.Combinatorica 12 (1992), 125-134. Zbl 0756.05049, MR 1179249, 10.1007/BF01204715 |
| Reference: | [3] Cushing, W., Kierstead, H. A.: Planar graphs are 1-relaxed, 4-choosable.Eur. J. Comb. 31 (2010), 1385-1397. Zbl 1221.05077, MR 2644426, 10.1016/j.ejc.2009.11.013 |
| Reference: | [4] Ding, G., Liu, C.: Excluding a small minor.Discrete Appl. Math. 161 (2013), 355-368. Zbl 1255.05185, MR 2998437, 10.1016/j.dam.2012.09.001 |
| Reference: | [5] Erdős, P., Rubin, A. L., Taylor, H.: Choosability in graphs.Combinatorics, Graph Theory and Computing Congressus Numerantium 26. Utilitas Mathematica Publishing, Winnipeg (1980), 125-157. Zbl 0469.05032, MR 0593902 |
| Reference: | [6] Grytczuk, J., Zhu, X.: The Alon-Tarsi number of a planar graph minus a matching.J. Comb. Theory, Ser. B 145 (2020), 511-520. Zbl 1448.05050, MR 4152773, 10.1016/j.jctb.2020.02.005 |
| Reference: | [7] Gu, Y., Zhu, X.: The Alon-Tarsi number of planar graphs revisited.J. Graph Theory 105 (2024), 398-402. Zbl 1531.05079, MR 4692716, 10.1002/jgt.23047 |
| Reference: | [8] Hefetz, D.: On two generalizations of the Alon-Tarsi polynomial method.J. Comb. Theory, Ser. B 101 (2011), 403-414. Zbl 1234.05086, MR 2832809, 10.1016/j.jctb.2010.12.007 |
| Reference: | [9] Jensen, T. R., Toft, B.: Graph Coloring Problems.John Wiley & Sons, New York (1995). Zbl 0855.05054, MR 1304254, 10.1002/9781118032497 |
| Reference: | [10] Kim, R., Kim, S.-J., Zhu, X.: The Alon-Tarsi number of subgraphs of a planar graph.Available at https://arxiv.org/abs/1906.01506 (2019), 12 pages. 10.48550/arXiv.1906.01506 |
| Reference: | [11] Kühn, D., Osthus, D.: Forcing unbalanced complete bipartite minors.Eur. J. Comb. 26 (2005), 75-81. Zbl 1061.05087, MR 2101035, 10.1016/j.ejc.2004.02.002 |
| Reference: | [12] Steiner, R.: Disproof of a conjecture by Woodall on the choosability of $K_{s,t}$-minor-free graphs.Electron. J. Comb. 29 (2022), Article ID 3.2, 11 pages. Zbl 1492.05052, MR 4446712, 10.37236/10994 |
| Reference: | [13] Thomassen, C.: Every planar graph is 5-choosable.J. Comb. Theory, Ser. B 62 (1994), 180-181. Zbl 0805.05023, MR 1290638, 10.1006/jctb.1994.1062 |
| Reference: | [14] Vizing, V. G.: Coloring the vertices of a graph in prescribed colors.Metody Diskretn. Anal. 29 (1976), 3-10 Russian. Zbl 0362.05060, MR 0498216 |
| Reference: | [15] Voigt, M.: List colourings of planar graphs.Discrete Math. 120 (1993), 215-219. Zbl 0790.05030, MR 1235909, 10.1016/0012-365X(93)90579-I |
| Reference: | [16] Wagner, K.: Über eine Eigenschaft der ebenen Komplexe.Math. Ann. 114 (1937), 570-590 German. Zbl 0017.19005, MR 1513158, 10.1007/BF01594196 |
| Reference: | [17] Woodall, D. R.: List colourings of graphs.Surveys in Combinatorics London Mathematical Society Lecture Note Series 288. Cambridge University Press, Cambridge (2001), 269-301. Zbl 0979.05047, MR 1850711, 10.1017/CBO9780511721328.012 |
| Reference: | [18] Zhu, X.: The Alon-Tarsi number of planar graphs.J. Comb. Theory, Ser. B 134 (2019), 354-358. Zbl 1402.05051, MR 3906645, 10.1016/j.jctb.2018.06.004 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
