PROPERTIES OF UNIQUELY K-LIST COLORABLE COMPLETE SPLIT GRAPHS

Authors

  • Lê Xuân Hùng Hanoi University of Natural Resources and Evironment, Viet Nam

DOI:

https://doi.org/10.37569/DalatUniversity.10.2.572(2020)

Keywords:

List coloring, Split graph, Uniquely k-list colorable graphs, Vertex coloring.

Abstract

Let G be a graph with n vertices. Suppose that for each vertex v in G there exists a list L(v) of k colors, such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. A graph G is called a split graph if there exists a partition V = I È K such that the subgraphs of G induced by I and K are empty and complete, respectively. The notion of split graphs was introduced in 1977 by S. Foldes and P. L. Hammer, and these graphs have since received much attention in graph theory. In this paper, we characterize the properties of complete split graphs that are uniquely k-list colorable graphs.

Downloads

Download data is not yet available.

References

Behazad, M., & Chartrand, G. (1971). Introduction to the theory of graphs. Boston, USA: Allyn and Bacon Publisher.

Chvatal, V., & Hammer, P. L. (1977). Aggregation of inequalities in integer programming. Annals of Discrete Mathematics, 1, 145-162.

Erdos, P., Rubin, A. L., & Taylor, H. (1979). Choosability in graphs. Paper presented at The West Coast Conference on Combinatorics, Graph Theory, and Computing, USA.

Foldes, S., & Hammer, P. L. (1977). Split graphs. Paper presented at The 8th Southeastern Conference on Combinatorics, Graph Theory, and Computing, USA.

Foldes, S., & Hammer, P. L. (1978). On a class of matroid-producing graphs. Colloquium of the Janos Bolyai Mathematical Society, 18, 331-352.

Henderson, P. B., & Zalcstein, Y. (1977). A graph-theoretic characterization of the PVchunk class of synchroniring primitive. SIAM Journal on Computing, 6(1), 88-108.

Hesham, A., & Hesham, E. R. (1993). Task allocation in distributed systems: A split graph model. Journal of Combinatorial Mathematics and Combinatorial Computing, 14, 15-32.

Lê, X. H. (2014). Sắc số, đa thức tô màu, và tính duy nhất tô màu của đồ thị tách cực. Tạp chí Khoa học và Giáo dục, 13(4), 23-27.

Lê, X. H. (2016). Tô màu danh sách của đồ thị tách cực. Tạp chí Khoa học và Công nghệ, (106), 78-80.

Lê, X. H. (2018). Chu trình Hamilton trong đồ thị tách cực. Tạp chí Khoa học và Công nghệ, (124), 94-97.

Mahmoodian, E. S., & Mahdian, M. (1997). On the uniquely list colorable graphs. Paper presented at The 28 Annual Iranian Mathematical Conference, Iran.

Ngo, D. T., & Le, X. H. (2004). Hamilton cycles in split graphs with large minimum degree. Discussiones Mathematics Graph Theory, 24(1), 23-40.

Ngo, D. T., & Le, X. H. (2005). On the Burkard-Hammer codition for Hamiltonian split graphs. Discrete Mathematics, 296(1), 59-72.

Peled, U. N. (1975). Regular Boolean functions and their polytope (PhD. thesis). University of Waterloo, Canada.

Published

04-05-2020

Volume and Issues

Section

Natural Sciences and Technology

How to Cite

Hùng, L. X. (2020). PROPERTIES OF UNIQUELY K-LIST COLORABLE COMPLETE SPLIT GRAPHS. Dalat University Journal of Science, 10(2), 85-93. https://doi.org/10.37569/DalatUniversity.10.2.572(2020)