Uniquely List Colorability of Complete Split Graphs

• Xuan Hung, Le ^[1]
  1. [1] HaNoi University for Natural Resources and Environment 41 A, Phu Dien Road, Phu Dien precinct, North Tu Liem district, Hanoi, Vietnam.
• Localización: Selecciones Matemáticas, ISSN-e 2411-1783, Vol. 8, Nº. 1, 2021 (Ejemplar dedicado a: Enero-Julio), págs. 120-124
• Idioma: inglés
• DOI: 10.17268/sel.mat.2021.01.11
• Enlaces
  • Texto completo (pdf)
• Resumen

  • 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.

• Referencias bibliográficas
  • 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.,...
  • Földes S, Hammer P. On a class of matroid-producing graphs. In: Combinatorics; Proc. Fifth Hungarian Colloq. 1976; Keszthely; vol. 1, 331–352....
  • 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,...
  • 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;...
  • Wang W, Liu X. List-coloring based channel allocation for open-spectrum wireless networks. In Proceedings of the IEEE International Conference...
  • Wang Y, Shen Y, Zheng G, He W. On uniquely 4-list colorable complete multipartite graphs. Ars Combinatoria, 2009; vol.93:203–214.