Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
Alon-Tarsi number; $K_{3,3}$-minor-free graph; planar graph
Alon-Tarsi number; $K_{3,3}$-minor-free graph; planar graph
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.
References:
[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. DOI 10.1016/j.disc.2021.112764 | MR 4357324 | Zbl 1482.05094
[2] Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12 (1992), 125-134. DOI 10.1007/BF01204715 | MR 1179249 | Zbl 0756.05049
[3] Cushing, W., Kierstead, H. A.: Planar graphs are 1-relaxed, 4-choosable. Eur. J. Comb. 31 (2010), 1385-1397. DOI 10.1016/j.ejc.2009.11.013 | MR 2644426 | Zbl 1221.05077
[4] Ding, G., Liu, C.: Excluding a small minor. Discrete Appl. Math. 161 (2013), 355-368. DOI 10.1016/j.dam.2012.09.001 | MR 2998437 | Zbl 1255.05185
[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. MR 0593902 | Zbl 0469.05032
[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. DOI 10.1016/j.jctb.2020.02.005 | MR 4152773 | Zbl 1448.05050
[7] Gu, Y., Zhu, X.: The Alon-Tarsi number of planar graphs revisited. J. Graph Theory 105 (2024), 398-402. DOI 10.1002/jgt.23047 | MR 4692716 | Zbl 1531.05079
[8] Hefetz, D.: On two generalizations of the Alon-Tarsi polynomial method. J. Comb. Theory, Ser. B 101 (2011), 403-414. DOI 10.1016/j.jctb.2010.12.007 | MR 2832809 | Zbl 1234.05086
[9] Jensen, T. R., Toft, B.: Graph Coloring Problems. John Wiley & Sons, New York (1995). DOI 10.1002/9781118032497 | MR 1304254 | Zbl 0855.05054
[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. DOI 10.48550/arXiv.1906.01506
[11] Kühn, D., Osthus, D.: Forcing unbalanced complete bipartite minors. Eur. J. Comb. 26 (2005), 75-81. DOI 10.1016/j.ejc.2004.02.002 | MR 2101035 | Zbl 1061.05087
[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. DOI 10.37236/10994 | MR 4446712 | Zbl 1492.05052
[13] Thomassen, C.: Every planar graph is 5-choosable. J. Comb. Theory, Ser. B 62 (1994), 180-181. DOI 10.1006/jctb.1994.1062 | MR 1290638 | Zbl 0805.05023
[14] Vizing, V. G.: Coloring the vertices of a graph in prescribed colors. Metody Diskretn. Anal. 29 (1976), 3-10 Russian. MR 0498216 | Zbl 0362.05060
[15] Voigt, M.: List colourings of planar graphs. Discrete Math. 120 (1993), 215-219. DOI 10.1016/0012-365X(93)90579-I | MR 1235909 | Zbl 0790.05030
[16] Wagner, K.: Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1937), 570-590 German. DOI 10.1007/BF01594196 | MR 1513158 | Zbl 0017.19005
[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. DOI 10.1017/CBO9780511721328.012 | MR 1850711 | Zbl 0979.05047
[18] Zhu, X.: The Alon-Tarsi number of planar graphs. J. Comb. Theory, Ser. B 134 (2019), 354-358. DOI 10.1016/j.jctb.2018.06.004 | MR 3906645 | Zbl 1402.05051
Search
Partner of
