PROPERTIES OF UNIQUELY K-LIST COLORABLE COMPLETE SPLIT GRAPHS
Keywords:List coloring, Split graph, Uniquely k-list colorable graphs, Vertex coloring.
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.
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.
Volume and Issues
Copyright & License
Copyright (c) 2020 Lê Xuân Hùng.
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.