Uniquely List Colorability of Complete Split Graphs


  • Le Xuan Hung HaNoi University for Natural Resources and Environment 41 A, Phu Dien Road, Phu Dien precinct, North Tu Liem district, Hanoi, Vietnam.




Chromatic number, list-chromatic number, uniquely list colorable graph, complete split graph


The join of null graph Om and complete graph Kn, denoted by S(m; n), is called a complete split graph. In this paper, we characterize unique list colorability of the graph G = S(m; n). We shall prove that G is uniquely 3-list colorable graph if and only if m>=4, n>=4 and m + n>=10, m(G)>=4 for every 1<=m<=5 and n>=6.


Behzad M, Chartrand G. Introduction to the theory of graphs. Bodton: Allyn and Bacon; 1971.

Brandstädt A, Hammer P, Le V, Lozin V. Bisplit graphs. Discrete Math. 1005; 299:11–32.

Chen B, Fu H, Ko M. Total chromatic number and chromatic index of split graphs. J. Combin. Math. Combin. Comput. 1995; 17:137–146.

Burkard R, Hammer P. A note on hamiltonian split graphs. J. Combin. Theory Ser. 1980; B 28:245–248.

Chvatal V, Hammer P. Aggregation of inequalities in integer programming. Annals Disc. Math. 1977; 1:145–162.

Dinitz J, Martin W. The stipulation polynomial of a uniquely list colorable graph. Austran. J. Combin. 1995; 11:105–115.

Földes S, Hammer P. Split graphs. In: Proc. Eighth Southeastern Conf. on Combin., Graph Theory and Computing; 1977; Louisiana State Univ., Baton Rouge. p 311–315.

Földes S, Hammer P. On a class of matroid-producing graphs. In: Combinatorics; Proc. Fifth Hungarian Colloq. 1976; Keszthely; vol. 1, 331–352. Colloq. Math. Soc. Jan´os Bolyai 18, North-Holland, Amsterdam–New York 1978.

Ghebleh M, Mahmoodian E. On uniquely list colorable graphs. Ars Combin. 2001; 59:307–318.

He W, Wang Y, Shen Y, Ma X. On property M(3) of some complete multipartite graphs. Australasian Journal of Combinatorics, to appear.

Henderson P, Zalcstein Y. A graph-theoretic characterization of the PVchunk class of synchronizing primitive. SIAM J. Comput. 1977; 6:88–108.

Hesham A, Hesham EL-R. Task allocation in distributed systems: a split graph model. J. Combin. Math. Combin. Comput. 1993; 14:15-32.

Hung L. List-chromatic number and chromatically unique of the graph Kr2 + Ok. Selecciones Matemáticas, Universidad Nacional de Trujillo, 2019; Vol. 06(01):26-30.

Hung L. Colorings of the graph Km 2 +Kn. Journal of Siberian Federal University. Mathematics & Physics 2020, 13(3):297–305.

Kratsch D, Lehel J, M¨uller H. Toughness, hamiltonicity and split graphs. Discrete Math. 150 (1996) 231–245.

Mahdian M, Mahmoodian E. A characterization of uniquely 2-list colorable graphs. Ars Combin. 1999; 51:295–305.

Peemöller J. Necessary conditions for hamiltonian split graphs. Discrete Math. 1985; 54:39–47.

Peled U. Regular Boolean functions and their polytope.[Ph. D. Thesis]. Dept. Combin. and Optimization of Univ. of Waterloo; 1975.

Shen Y, Wang Y. On uniquely list colorable complete multipartite graphs. Ars Combin. 2008; 88:367–377.

Tan N, Hung L. Hamilton cycles in split graphs with large minimum degree. Discussiones Mathematicae Graph Theory, 2004; 24:23–40.

Tan N, Hung L. On the Burkard-Hammer condition for hamiltonian split graphs. Discrete Mathematics, 2005; 296:59–72.

Tan N, Hung L. On colorings of split graphs. Acta Mathematica Vietnammica, 2006; Volume 31(3):195–204.

Wang Y, Wang Y, Zhang X. Some conclusion on unique k-list colorable complete multipartite graphs. J. Appl. Math. 2013; Art. ID 380,861 pp.5; DOI http://dx.doi.org/10.1155/2013/380861

Wang W, Liu X. List-coloring based channel allocation for open-spectrum wireless networks. In Proceedings of the IEEE International Conference on Vehicular Technology, 2005; (VTC ‘05):690 – 694.

Wang Y, Shen Y, Zheng G, He W. On uniquely 4-list colorable complete multipartite graphs. Ars Combinatoria, 2009; vol.93:203–214.




How to Cite

Xuan Hung, L. (2021). Uniquely List Colorability of Complete Split Graphs. Selecciones Matemáticas, 8(01), 120 - 124. https://doi.org/10.17268/sel.mat.2021.01.11