Uniquely List Colorability of Complete Split Graphs
DOI:
https://doi.org/10.17268/sel.mat.2021.01.11Palavras-chave:
Chromatic number, list-chromatic number, uniquely list colorable graph, complete split graphResumo
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.
Referências
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
Publicado
Como Citar
Edição
Seção
Licença
Copyright (c) 2021 Le Xuan Hung
Este trabalho está licenciado sob uma licença Creative Commons Attribution 4.0 International License.
Os autores que publicam nesta revista aceitam as seguintes condições:
Os autores mantêm os direitos autorais e atribuem à revista o direito da primeira publicação, com o trabalho registrado com a licença de atribuição Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite que terceiros usem o material publicado sempre que mencionarem a autoria do trabalho e os direitos autorais. Primeira publicação nesta revista.
Os autores podem fazer outros acordos contratuais independentes e adicionais para a distribuição não exclusiva da versão do artigo publicada nesta revista (por exemplo, incluí-la em um repositório institucional ou publicá-la em um livro), desde que afirme claramente que o trabalho Foi publicado nesta revista.
É permitido e recomendado aos autores que publiquem seus trabalhos na Internet (por exemplo, em páginas institucionais ou pessoais) antes e durante o processo de revisão e publicação, pois isso pode levar a trocas produtivas e a uma disseminação maior e mais rápida do trabalho. publicado (Consultar: efeito do acesso aberto).
