Uniquely list colorability of complete tripartite graphs
https://doi.org/10.22405/2226-8383-2022-23-2-170-178
Abstract
Given a list 𝐿(𝑣) for each vertex 𝑣, we say that the graph 𝐺 is 𝐿-colorable if there is a proper vertex coloring of G where each vertex 𝑣 takes its color from 𝐿(𝑣). The graph is uniquely 𝑘-list
colorable if there is a list assignment 𝐿 such that |𝐿(𝑣)| = 𝑘 for every vertex 𝑣 and the graph has exactly one 𝐿-coloring with these lists. If a graph 𝐺 is not uniquely 𝑘-list colorable, we also
say that 𝐺 has property 𝑀(𝑘). The least integer 𝑘 such that 𝐺 has the property 𝑀(𝑘) is called the 𝑚-number of 𝐺, denoted by 𝑚(𝐺). In this paper, first we characterize about the property of
the complete tripartite graphs when it is uniquely 𝑘-list colorable graphs, finally we shall prove that 𝑚(𝐾2,2,𝑚) = 𝑚(𝐾2,3,𝑛) = 𝑚(𝐾2,4,𝑝) = 𝑚(𝐾3,3,3) = 4 for every 𝑚 > 9, 𝑛 > 5, 𝑝 > 4.
References
1. M. Behzad, 1965, “Graphs and thei chromatic number”, Doctoral Thesis (Michigan State University).
2. M. Behzad and G. Chartrand, 1971, “Introduction to the theory of graphs”, Allyn and Bacon, Boston.
3. M. Behzad, G. Chartrand and J. Cooper, 1967, “The coloring numbers of complete graphs”, J. London Math. Soc. № 42, pp. 226 – 228.
4. J.A. Bondy and U.S.R. Murty, 1976, “Graph theory with applications”, MacMillan.
5. R. Diestel, 2000, “Graph Theory”, Springer – Verlag New York.
6. J.H. Dinitz and W.J. Martin, 1995, “The stipulation polynomial of a uniquely list colorable graph”, Austran. J. Combin. № 11, pp. 105–115.
7. P. Erd¨os, A. L. Rubin, and H. Taylor, 1979, “Choosability in graphs”. In Proceedings of west coast conference on combinatorics, graph theory, and computing, number 26 in Congr. Numer., pp. 125–157, Arcata, CA.
8. M. Ghebleh and E.S. Mahmoodian, 2001, “On uniquely list colorable graphs”, Ars Combin. № 59, pp. 307–318.
9. Le Xuan Hung, “Colorings of the graph 𝐾𝑚2 + 𝐾𝑛”, Journal of Siberian Federal University. Mathematics & Physics, to appear.
10. M. Mahdian and E.S. Mahmoodian, 1999, “A haracterization of uniquely 2-list colorable graphs”, Ars Combin. № 51, pp. 295–305.
11. R.C. Read, 1968, “An introduction to chromatic polynomials”, J. Combin. Theory, № 4, pp. 52–71.
12. Ngo Dac Tan and Le Xuan Hung, 2006, “On colorings of split graphs”, Acta Mathematica Vietnammica, Volume 31, № 3, pp. 195 – 204.
13. V.G. Vizing, 1964, “On an estimate of the chromatic class of a 𝑝-graph”, Discret. Analiz. № 3, pp. 23–30. (In Russian).
14. V. G. Vizing ,1976, “Coloring the vertices of a graph in prescribed colors”. In Diskret. Analiz, number 29 in Metody Diskret. Anal. v Teorii Kodov i Shem, pp. 3–10.
15. W. Wang and X. Liu, 2005, “List-coloring based channel allocation for open-spectrum wireless networks
16. , in Proceedings of the IEEE International Conference on Vehicular Technology (VTC ’05), pp. 690 – 694.
17. R.J. Wilson, 1975, Introduction to graph theory, Longman group ltd, London.
18. Yancai Zhao and Erfang Shan, 2010, “On characterization of uniquely 3-list colorable complete multipartite graphs”, Discussiones Mathematicae Graph Theory, № 30, pp. 105–114.
19. Y.Q. Zhao, W.J. He, Y.F. Shen and Y.N. Wang, 2007, “Note on characterization of uniquely 3-list colorable complete multipartite graphs”, in: Discrete Geometry, Combinatorics and Graph Theory, LNCS 4381 (Springer, Berlin, pp. 278–287.
Review
For citations:
Hung X. Uniquely list colorability of complete tripartite graphs. Chebyshevskii Sbornik. 2022;23(2):170-178. (In Russ.) https://doi.org/10.22405/2226-8383-2022-23-2-170-178
Views:
279
Email this article 