The chromaticity of complete split graphs
https://doi.org/10.22405/2226-8383-2024-25-2-208-221
Abstract
The join of null graph 𝑂𝑚 and complete graph 𝐾𝑛, 𝑂𝑚+𝐾𝑛 = 𝑆(𝑚, 𝑛), is called a complete split graph. In this paper, we characterize chromatically unique, determine list-chromatic number and characterize unique list colorability of the complete split graph 𝐺 = 𝑆(𝑚, 𝑛). We shall prove that 𝐺 is chromatically unique if and only if 1 ⩽ 𝑚 ⩽ 2, 𝑐ℎ(𝐺) = 𝑛 + 1, 𝐺 is uniquely 3-list colorable graph if and only if 𝑚 ⩾ 4, 𝑛 ⩾ 4 and 𝑚+𝑛 ⩾ 10, 𝑚(𝐺) ⩽ 4 for every 1 ⩽ 𝑚 ⩽ 5 and 𝑛 ⩾ 6. Some the property of the graph 𝐺 = 𝑆(𝑚, 𝑛) when it is 𝑘-list colorable graph also proved.
References
1. Behzad, M., 1965, Graphs and thei chromatic number. Doctoral Thesis (Michigan State
2. University).
3. Behzad, M., Chartrand, G., 1971. “Introduction to the theory of graphs”, Allyn and Bacon,
4. Boston.
5. Behzad, M., Chartrand, G., Cooper, J., 1967. “The coloring numbers of complete graphs”, J.
6. London Math. Soc. 42, pp. 226 – 228.
7. Birkhoff, G. D., 1912. “A determinant formula for the number of ways of coloring a map”, Annals of Math., 14 (2), pp. 42–46.
8. Bondy, J. A., Murty, U.S.R., 1976. “Graph theory with applications”, MacMillan.
9. Brandst¨adt, A., Hammer, P. L., Le, V. B., Lozin, V. V., 2005. “Bisplit graphs”, Discrete Math.,
10. , pp. 11–32.
11. Chen, B.-L., Fu, H.-L., Ko, M. T., 1995. “Total chromatic number and chromatic index of split
12. graphs”, J. Combin. Math. Combin. Comput., 17, pp. 137–146.
13. Brent, F., 1992. “Expansions of chromatic polynomial and log-concavity”, Trans. Amer. Math. Soc. 332, pp. 729 – 756.
14. Burkard, R. E., Hammer, P. L., 1980. “A note on hamiltonian split graphs”, J. Combin. Theory Ser. Vol. 28, pp. 245–248.
15. Chao, C. Y., Whitehead, Jr. E. G., 1978. “On chromatic equivalence of graphs”, Theory and Applications of Graphs, ed. Y. Alavi and D.R. Lick, Springer Lecture Notes in Math. 642, pp. 121 – 131.
16. Chvatal, V., Hammer, P. L., 1977. “Aggregation of inequalities in integer programming”, Annals Disc. Math. 1, pp. 145–162.
17. Diestel, R., 2000. “Graph Theory”, Springer – Verlag New York.
18. Dinitz, J. H., Martin, W.J., 1995. “The stipulation polynomial of a uniquely list colorable graph”, Austran. J. Combin. 11, pp. 105–115.
19. F¨oldes, S., Hammer, P. L., 1977. “Split graphs”, Proc. Eighth Southeastern Conf. on Combin., Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La.), pp. 311–315.
20. Congressus Numerantium, No XIX, Utilitas Math., Winnipeg, Man., 1977.
21. F¨oldes, S., Hammer, P. L., 1976, 1978. “On a class of matroid-producing graphs”, Combinatorics (Proc. Fifth Hungarian Colloq.), Keszthely, vol. 1, 331–352., Colloq. Math. Soc. Jan´os Bolyai 18, North-Holland, Amsterdam–New York.
22. Ghebleh, M., Mahmoodian, E. S., 2001. “On uniquely list colorable graphs”, Ars Combin., 59, pp. 307–318.
23. He, W. J., Wang, Y. N., Shen, Y. F., Ma, X., “On property M(3) of some complete multipartite graphs”, Australasian Journal of Combinatorics, to appear.
24. Henderson, P.B., Zalcstein, Y., 1977. “A graph-theoretic characterization of the 𝑃𝑉_𝑐ℎ𝑢𝑛𝑘 class of synchronizing primitive”, SIAM J. Comput., 6, pp. 88–108.
25. Hesham, H. A., Hesham, El-R, 1993. “Task allocation in distributed systems: a split graph
26. model”, J. Combin. Math. Combin. Comput., 14, pp. 15–32.
27. Le Xuan Hung, 2019. “List-chromatic number and chromatically unique of the graph (𝐾_𝑟)^2 +𝑂_𝑘”,Selecciones Matem´aticas, Universidad Nacional de Trujillo, Vol. 06(01), pp. 26–30.
28. Le Xuan Hung, 2020. “Colorings of the graph (𝐾_𝑚)^2 +𝐾_𝑛”, Journal of Siberian Federal University. Mathematics & Physics, 13(3), pp. 297 – 305.
29. Le Xuan Hung, 2020. “The chromaticity of the join of tree and null graph”, Prikladnaya
30. Diskretnaya Matematika, № 50, pp. 93 – 101.
31. Le Xuan Hung, 2022. “Unique list colorability of the graph (𝐾_𝑛)^2 +𝐾_𝑟”, Prikladnaya Diskretnaya Matematika, № . 55, pp. 88 – 94.
32. Le Xuan Hung, 2022, “Uniquely list colorability of complete tripartite graphs”, Chebyshevskii sbornik, vol. 23, no. 2, pp. 170–178.
33. Koh, K. M., Teo, K. L., 1990. “The search for chromatically unique graphs”, Graphs Combin., 6, pp. 259 – 285.
34. Koh, K. M., Teo, K. L., 1997. “The search for chromatically unique graphs II”, Discrete Math., 172, pp. 59 – 78.
35. Kratsch, D., Lehel, J., M¨uller, H., 1996. “Toughness, hamiltonicity and split graphs”, Discrete Math., 150, pp. 231–245.
36. Liu, R. Y., 1987. “A new method to find the chromatic polynomial of a graphand its
37. applications”, Kexue Tongbao, 32, pp. 1508 – 1509.
38. Mahdian, M., Mahmoodian, E. S., 1999. “A characterization of uniquely 2-list colorable graphs”, Ars Combin., 51, pp. 295–305.
39. Peem¨oller, J., 1985. “Necessary conditions for hamiltonian split graphs”, Discrete Math., 54, pp. 39–47.
40. Peled, U. N., 1975. “Regular Boolean functions and their polytope”, Chapter VI, Ph. D. Thesis, Univ. of Waterloo, Dept. Combin. and Optimization.
41. Read, R. C., 1968. “An introduction to chromatic polynomials”, J. Combin. Theory, 4 (1968), pp. 52 – 71.
42. Shen, Y. F., Wang, Y. N., 2008. “On uniquely list colorable complete multipartite graphs”, Ars Combin., 88, pp. 367–377.
43. Ngo Dac Tan and Le Xuan Hung, 2004. “Hamilton cycles in split graphs with large minimum degree”, Discussiones Mathematicae Graph Theory, 24, pp. 23 – 40.
44. Ngo Dac Tan and Le Xuan Hung, 2005. “On the Burkard-Hammer condition for hamiltonian split graphs”, Discrete Mathematics, 296, pp. 59 – 72.
45. Ngo Dac Tan and Le Xuan Hung, 2006. “On colorings of split graphs”, Acta Mathematica
46. Vietnammica, Vol. 31, № . 3, pp. 195 – 204.
47. Vizing, V. G., 1964. “On an estimate of the chromatic class of a 𝑝-graph”, Discret. Analiz., 3, pp. 23–30. (In Russian)
48. Wang, Y., Wang, Y., Zhang, X., 2013. “Some conclusion on unique k-list colorable complete multipartite graphs”, J. Appl. Math., pp. 5, Art. ID 380,861. DOI http://dx.doi.org/10.1155/2013/380861
49. Wang, Y., Shen, Y., Zheng, G., He, W., 2009. “On uniquely 4-list colorable complete multipartite graphs”, Ars Combinatoria, vol.93, pp. 203—214.
50. Wilson, R.J., 1975. “Introduction to graph theory”, Longman group ltd, London.
Review
For citations:
Hung X. The chromaticity of complete split graphs. Chebyshevskii Sbornik. 2024;25(2):208-221. (In Russ.) https://doi.org/10.22405/2226-8383-2024-25-2-208-221
Views:
269
Email this article 