Uniquely list colorability of the graph Kn2 + Om

• 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. 7, Nº. 1, 2020 (Ejemplar dedicado a: January - July), págs. 25-28
• Idioma: inglés
• DOI: 10.17268/sel.mat.2020.01.03
• Enlaces
  • Texto completo (pdf)
• Resumen

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

• Referencias bibliográficas
  • 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,...
  • 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....
  • 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....
  • Wang W, Liu X. List-coloring based channel allocation for open-spectrum wireless networks. In Proceedings of the IEEE International Conference...
  • 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;...