Uniquely List Colorability of Complete Split Graphs
DOI:
https://doi.org/10.17268/sel.mat.2021.01.11Keywords:
Chromatic number, list-chromatic number, uniquely list colorable graph, complete split graphAbstract
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.
References
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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Le Xuan Hung
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors who publish in this journal accept the following conditions:
1. The authors retain the copyright and assign to the journal the right of the first publication, with the work registered with the Creative Commons Attribution License,Atribución 4.0 Internacional (CC BY 4.0) which allows third parties to use what is published whenever they mention the authorship of the work And to the first publication in this magazine.
2. Authors may make other independent and additional contractual arrangements for non-exclusive distribution of the version of the article published in this journal (eg, include it in an institutional repository or publish it in a book) provided they clearly state that The paper was first published in this journal.
3. Authors are encouraged to publish their work on the Internet (for example, on institutional or personal pages) before and during the review and publication process, as it can lead to productive exchanges and to a greater and more rapid dissemination Of the published work.
