PROPERTIES OF UNIQUELY K-LIST COLORABLE COMPLETE SPLIT GRAPHS

Lê Xuân Hùng

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.


Keywords


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

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.




DOI: http://dx.doi.org/10.37569/DalatUniversity.10.2.572(2020)

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Lê Xuân Hùng.

License URL: https://creativecommons.org/licenses/by-nc/4.0/
Editorial Office of DLU Journal of Science
Room.15, A25 Building, 01 Phu Dong Thien Vuong Street, Dalat, Lamdong
Email: tapchikhoahoc@dlu.edu.vn - Phone: (+84) 263 3 555 131

Creative Commons License
Based on Open Journal Systems
Developed by Information Technology Department