Uniquely List Colorability of Complete Split Graphs
DOI:
https://doi.org/10.17268/sel.mat.2021.01.11Palabras clave:
Chromatic number, list-chromatic number, uniquely list colorable graph, complete split graphResumen
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.
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2021 Le Xuan Hung
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
- Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative CommonsAtribución 4.0 Internacional (CC BY 4.0) , que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado(Consultar: efecto del acceso abierto).
