magazinelogo

Journal of Applied Mathematics and Computation

ISSN Print: 2576-0645 Downloads: 146180 Total View: 1802025
Frequency: quarterly ISSN Online: 2576-0653 CODEN: JAMCEZ
Email: jamc@hillpublisher.com
Article Open Access http://dx.doi.org/10.26855/jamc.2023.03.018

The Alon-Tarsi Number of the Mycielski Graphs

Zhiguo Li*, Qing Ye, Zeling Shao

School of Science, Hebei University of Technology, Tianjin, China.

*Corresponding author: Zhiguo Li

Published: May 6,2023

Abstract

The Alon-Tarsi number AT(G) of a graph G is the least k for which there is an orientation D of G with max outdegree K-1  such that the number of spanning Eulerian subgraphs of G with an even number of edges differs from the number of spanning Eulerian subgraphs with an odd number of edges. A graph G is said to be chromatic-ATchoosable if . In this paper, it is shown that the Alon-Tarsi number of the Mycielski graph M(G) is at most , where  is the maximum degree of G. As a consequence, M(G) is -choosable. Based on analysis of the structure of Mycielskigraphs, the exact values of the Alon-Tarsi number of Mycielski graphs  and  are obtained by the method of the Alon-Tarsi orientation. It is proved that and are chromatic-AT choosable. On the other hand, we get that the Alon-Tarsi number of equals 5 when  and  otherwise.

References

[1] N. Alon, M. Tarsi. (1992). Colorings and orientations of graphs. Combinatorica, 12(2), 125-134.

[2] T. R. Jensen, B. Toft. (1995). Graph coloring problems. Wiley, New York.

[3] X. D. Zhu. (2019). The Alon-Tarsi number of planar graphs. Journal of Combinatorial Theory, Series B, 134, 354-358.

[4] J. Grytczuk, X. D. Zhu. (2020). The Alon-Tarsi number of a planar graph minus a matching. Journal of Combinatorial Theory, Series B, 145, 511-520.

[5] Z. G. Li, Z. L. Shao, F. Petrov, A. Gordeev. (2023). The Alon-Tarsi number of a toroidal grid. European Journal of Combina-torics, https://doi.org/10.1016/j.ejc.2023.103697.

[6] T. Abe, S. J. Kim, K. Ozeki. (2022). The Alon-Tarsi number of -minor-free graphs.Discrete Mathematics, 345(4), 112764.

[7] Y. S. Kwon, J. Lee, Z. F. Zhang. (2012). Edge-chromatic numbers of Mycielski graphs. Discrete Mathematics, 312(6), 1222-1225.

[8] J. Mycielski. (1955). Sur le colouriage des graphes. Colloquium Mathematicae, 3, 161-162.

[9] J. A. Allagan, B. Bobga, P. Johnson. (2015). On the choosability of some graphs. Congressus Numerantium, 225, 95-100.

[10] J. Hladky, D. Kral, U. Schauz. (2010). Brooks' Theorem via the Alon-Tarsi Theorem. 

Discrete Mathematics, 310(23), 3426-3428.

[11] X. D. Zhu, R. Balakrishnan. (2021). Combinatorial Nullstellensatz: With Applications to Graph Coloring. Chapman and Hall/CRC.

[12] J. A. Bondy, U. S. R. Murty. (2008). Graph Theory. London, Springer.

[13] Z. G. Li, Q. Ye, Z. L. Shao. (2021). The Alon-Tarsi number of Halin graphs. https://doi.org/10.48550/arXiv.2110.11617.

[14] H. Kaul, J. A. Mudrock. (2019). On the Alon-Tarsi number and chromatic choosability of Cartesian products of graphs. The Electronic Journal of Combinatorics, 26(1), P1.3.

How to cite this paper

The Alon-Tarsi Number of the Mycielski Graphs

How to cite this paper: Zhiguo Li, Qing Ye, Zeling Shao. (2023) The Alon-Tarsi Number of the Mycielski Graphs. Journal of Applied Mathematics and Computation7(1), 162-166.

DOI: http://dx.doi.org/10.26855/jamc.2023.03.018