Uniquely list colorability of the graph Kn2 + Om
DOI:
https://doi.org/10.17268/sel.mat.2020.01.03Palabras clave:
Vertex coloring (coloring), list coloring, uniquely list colorable graph, complete r-partite graphResumen
Given a list L(v) for each vertex v, we say that the graph G is L-colorable if there is a proper vertex coloring of G where each vertex v takes its color from L(v). The graph is uniquely k-list colorable if there is a list assignment L such that jL(v)j = k for every vertex v and the graph has exactly one L-coloring with these lists. In this paper, we characterize uniquely list colorability of the graph G = Kn2 + Om. We shall prove that if n = 2 then G is uniquely 3-list colorable if and only if m >= 9, if n = 3 and m >=1 then G is uniquely 3-list colorable, if n >=4 then G is uniquely k-list colorable with k =[m/2]+1, and if m>=n-1, entonce G es UnLC.
Citas
Behzad M. Graphs and thei chromatic number. Doctoral Thesis (Michigan State University), 1965.
Behzad M, Chartrand G. Introduction to the theory of graphs. Allyn and Bacon, Boston, 1971.
Behzad M, Chartrand G, Cooper J. The coloring numbers of complete graphs. J. London Math. Soc. 1967; 42:226–228.
Bondy J, Murty U. Graph theory with applications. MacMillan, 1976.
Diestel R. Graph Theory, Springer – Verlag New Your, 2000.
Dinitz J. Martin W. The stipulation polynomial of a uniquely list colorable graph. Austran. J. Combin. 1995; 11:105–115.
Erdös P, Rubin A, Taylor H. (1979) Choosability in graphs. In Proceedings of west coast conference on combinatorics, graph theory, and computing, number 26 in Congr. Numer. pages 125–157, Arcata, CA, September.
Ghebleh M, Mahmoodian E. On uniquely list colorable graphs. Ars Combin. 2001; 59:307–318.
Hung L. List-chromatic number and chromatically unique of the graph Kr2 + Ok. Selecciones Matemáticas, Universidad Nacional de Trujillo. 2019; 06(01):26–30.
Mahdian M, Mahmoodian E. A characterization of uniquely 2-list colorable graphs. Ars Combin. 1999; 51:295-305.
Read R. (1968) An introduction to chromatic polynomials. J. Combin. Theory. 1968; 4:52–71.
Tan N, Hung L. On colorings of split graphs. Acta Mathematica Vietnammica. 2006; 31(3):195–204.
Vizing V. On an estimate of the chromatic class of a p-graph. Discret. Analiz. 1964; 3:23–30.
Vizing V. Coloring the vertices of a graph in prescribed colors. In Diskret. Analiz, number 29 in Metody Diskret. Anal. v Teorii Kodov i Shem. 1976; 3–10.
Wang W, Liu X. List-coloring based channel allocation for open-spectrum wireless networks. In Proceedings of the IEEE International Conference on Vehicular Technology (VTC ’05). 2005; 690-694.
Wilson R. Introduction to graph theory. Longman group ltd, London, 1975.
Zhao Y, Shan E. On characterization of uniquely 3-list colorable complete multipartite graphs. Discussiones Mathematicae Graph Theory. 2010; 30:105–114.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
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).
