The chromaticity of complete split graphs

Hung Xuan Le

Čebyševskij sbornik, Tome 25 (2024) no. 2, pp. 208-221.

Résumé

The join of null graph $O_m$ and complete graph $K_n$, $O_m+K_n=S(m,n)$, 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 $G=S(m,n)$. We shall prove that $G$ is chromatically unique if and only if $1\le m\le 2$, $ch(G)=n+1$, $G$ is uniquely $3$-list colorable graph if and only if $m\ge 4$, $n\ge 4$ and $m+n\ge 10$, $m(G)\le 4$ for every $1\le m\le 5$ and $n\ge 6$. Some the property of the graph $G=S(m,n)$ when it is $k$-list colorable graph also proved.

Détail

Keywords: chromatically unique, list- chromatic number, uniquely list colorable graph, complete split graph.

Bibliographie

[1] Behzad, M., Graphs and thei chromatic number, Doctoral Thesis, Michigan State University, 1965

[2] Behzad, M., Chartrand, G., Introduction to the theory of graphs, Allyn and Bacon, Boston, 1971

[3] Behzad, M., Chartrand, G., Cooper, J., “The coloring numbers of complete graphs”, J. London Math. Soc., 42 (1967), 226–228

[4] Birkhoff, G. D., “A determinant formula for the number of ways of coloring a map”, Annals of Math., 14:2 (1912), 42–46

[5] Bondy, J. A., Murty, U.S.R., Graph theory with applications, MacMillan, 1976

[6] Brandstädt, A., Hammer, P. L., Le, V. B., Lozin, V. V., “Bisplit graphs”, Discrete Math., 299 (2005), 11–32 | DOI | MR | Zbl

[7] Chen, B.-L., Fu, H.-L., Ko, M. T., “Total chromatic number and chromatic index of split graphs”, J. Combin. Math. Combin. Comput., 17 (1995), 137–146 | Zbl

[8] Brent, F., “Expansions of chromatic polynomial and log-concavity”, Trans. Amer. Math. Soc., 332 (1992), 729–756 | Zbl

[9] Burkard, R. E., Hammer, P. L., “A note on hamiltonian split graphs”, J. Combin. Theory Ser., 28 (1980), 245–248 | Zbl

[10] Chao, C. Y., Whitehead, Jr. E. G., “On chromatic equivalence of graphs”, Theory and Applications of Graphs, Springer Lecture Notes in Math., 642, eds. Y. Alavi, D.R. Lick, 1978, 121–131 | Zbl

[11] Chvatal, V., Hammer, P. L., “Aggregation of inequalities in integer programming”, Annals Disc. Math., 1 (1977), 145–162 | Zbl

[12] Diestel, R., Graph Theory, Springer-Verlag, New York, 2000

[13] Dinitz, J. H., Martin, W.J., “The stipulation polynomial of a uniquely list colorable graph”, Austran. J. Combin., 11 (1995), 105–115

[14] Földes, S., Hammer, P. L., Graph Theory and Computing, Congressus Numerantium, No XIX, Proc. Eighth Southeastern Conf. on Combin. (Louisiana State Univ., Baton Rouge, La), Utilitas Math., Winnipeg, Man, 1977, Split graphs

[15] Földes, S., Hammer, P. L., “On a class of matroid-producing graphs”, Combinatorics, Proc. Fifth Hungarian Colloq. (Keszthely, 1976), v. 1, Colloq. Math. Soc. Janós Bolyai, 18, North-Holland, Amsterdam–New York, 1978, 331–352

[16] Ghebleh, M., Mahmoodian, E. S., “On uniquely list colorable graphs”, Ars Combin., 59 (2001), 307–318

[17] He, W. J., Wang, Y. N., Shen, Y. F., Ma, X., “On property M(3) of some complete multipartite graphs", Australasian Journal of Combinatorics”

[18] Henderson, P.B., Zalcstein, Y., “A graph-theoretic characterization of the $PV_{chunk}$ class of synchronizing primitive”, SIAM J. Comput., 6 (1977), 88–108

[19] Hesham, H. A., Hesham, El-R., “Task allocation in distributed systems: a split graph model”, J. Combin. Math. Combin. Comput., 14 (1993), 15–32

[20] Le Xuan Hung, “List-chromatic number and chromatically unique of the graph $K^r_2+O_k$”, Selecciones Matemáticas, Universidad Nacional de Trujillo, 06(01):2 (2019), 26–30

[21] Le Xuan Hung, “Colorings of the graph $K^m_2+K_n$”, Journal of Siberian Federal University. Mathematics $\ $ Physics, 13:3 (2020), 297–305 | MR

[22] Le Xuan Hung, “The chromaticity of the join of tree and null graph”, Prikladnaya Diskretnaya Matematika, 2020, no. 50, 93–101

[23] Le Xuan Hung, “Unique list colorability of the graph $K^n_2+K_r$”, Prikladnaya Diskretnaya Matematika, 2022, no. 55, 88–94

[24] Le Xuan Hung, “Uniquely list colorability of complete tripartite graphs”, Chebyshevskii sbornik, 23:2 (2022), 170–178 | DOI | MR

[25] Koh, K. M., Teo, K. L., “The search for chromatically unique graphs”, Graphs Combin., 6 (1990), 259–285 | Zbl

[26] Koh, K. M., Teo, K. L., “The search for chromatically unique graphs II”, Discrete Math., 172 (1997), 59–78 | Zbl

[27] Kratsch, D., Lehel, J., Müller, H., “Toughness, hamiltonicity and split graphs”, Discrete Math., 150 (1996), 231–245

[28] Liu, R. Y., “A new method to find the chromatic polynomial of a graphand its applications”, Kexue Tongbao, 32 (1987), 1508–1509

[29] Mahdian, M., Mahmoodian, E. S., “A characterization of uniquely 2-list colorable graphs”, Ars Combin., 51 (1999), 295–305

[30] Peemöller, J., “Necessary conditions for hamiltonian split graphs”, Discrete Math., 54 (1985), 39–47

[31] Peled, U. N., Regular Boolean functions and their polytope, Chapter VI, Ph. D. Thesis, Univ. of Waterloo, Dept. Combin. and Optimization, 1975

[32] Read, R. C., “An introduction to chromatic polynomials”, J. Combin. Theory, 4 (1968), 52–71

[33] Shen, Y. F., Wang, Y. N., “On uniquely list colorable complete multipartite graphs”, Ars Combin., 88 (2008), 367–377 | Zbl

[34] Ngo Dac Tan, Le Xuan Hung, “Hamilton cycles in split graphs with large minimum degree”, Discussiones Mathematicae Graph Theory, 24 (2004), 23–40 | Zbl

[35] Ngo Dac Tan, Le Xuan Hung, “On the Burkard-Hammer condition for hamiltonian split graphs”, Discrete Mathematics, 296 (2005), 59–72 | Zbl

[36] Ngo Dac Tan and Le Xuan Hung, “On colorings of split graphs”, Acta Mathematica Vietnammica, 31:3 (2006), 195–204 | MR | Zbl

[37] Vizing, V. G., “On an estimate of the chromatic class of a $p$-graph”, Discret. Analiz, 3 (1964), 23–30 (In Russian)

[38] Wang, Y., Wang, Y., Zhang, X., “Some conclusion on unique k-list colorable complete multipartite graphs”, J. Appl. Math., 2013, 380 861, 5 pp. | DOI

[39] Wang, Y., Shen, Y., Zheng, G., He, W., “On uniquely $4$-list colorable complete multipartite graphs”, Ars Combinatoria, 93 (2009), 203–214

[40] Wilson, R.J., Introduction to graph theory, Longman group ltd, London, 1975 | MR