An investigation into the uniquely 2-list colorable of complete split graphs
Abstract: 16
##plugins.themes.academic_pro.article.main##
Author
Keywords:
Split graph
vertex coloring (coloring)
chromatic number
list coloring
uniquely k - list colorable graphs
Abstract
Let G be a graph with n vertices and suppose that for each vertex v in G, there exists a list of k colors, L(v) , 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=(V,E) is called a split graph if there exists a partition V=I U 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. These graphs have been paid attention in graph theory. Complete split graph with I=m, K=n is denoted by S(m,n). In this paper, we prove that is uniquely 2- list colorable if only if m>=2, n>=2 .
References
-
[1] M. Behazad and G. Chartrand, Introduction to the Theory of graphs, Allyn and Bacon, Boston, 1971.
[2] S. Foldes and P.L. Hammer, “Split graphs”, In: Proceeding of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State University, Baton Rouge, LA, 1977), Congressus Numerantium, vol. XIX, Utilitas Mathematics, Winnipeg, Man., 1977, pp. 311 – 315.
[3] V. Chvatal and P.L. Hammer, “Aggregation of inequalities in integer programming”, Ann. Discrete Math. 1, 1977, pp. 145 – 162.
[4] S. Foldes and P.L. Hammer, “On a class of matroid-producing graphs”, In: Combinatorics (Proceeding of the Filth Hungarian Colloquium, Kesrthely, 1976), vol. 1, Colloquium Mathematical Society, Jano’s Bolyai, vol. 18, North-Holland, Amsterdam, New York, 1978, pp. 331 - 352.
[5] U. N. Peled (1975), Regular Boolean functions and their polytope, Chapter VI, PH. D. Thesis, Univ. of Waterloo, Dept. Combin. And Optimization, 1975.
[6] P. B. Henderson and Y. Zalcstein, “A graph-theoretic characterization of the class of synchroniring primitive”, SIAM J. Comput. 6, 1977, pp. 88-108.
[7] A. Hesham H. and El-R. Hesham, “Task allocation in distributed systems: a split graph model”, J. Combin. Math. Combin. Comput. 14, 1993, pp. 15-32.
[8] P. Erdos, A. L. Rubin, and H. Taylor, “Choosability in graphs”, In Proceedings of west coast conference on combinatorics, graph theory, and computing, number 26 in Congr. Numer., 1979, pp. 125–157.
[9] E. S. Mahmoodian and M. Mahdian, “On the uniquely list colorable graphs”, In Proceedings of the 28th Annual Iranian Mathematics Conference, Part 1, number 377 in Tabriz Univ. Ser., 1997, pp. 319–326.
[10] Lê Xuân Hùng, “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(04), Trường Đại học Sư phạm, Đại học Đà Nẵng, 2014, trang 23 – 27.
[11] Lê Xuân Hùng, “Tô màu danh sách của đồ thị tách cực”, Tạp chí Khoa học và Công nghệ - Đại học Đà Nẵng, 9(106), 2016, trang 78 – 80.
[12] Lê Xuân Hùng, “Tính chất của đồ thị tách cực đầy đủ duy nhất k-tô màu danh sách”, Tạp chí Khoa học, Đại học Đà Lạt, Tập 10 (Số 2), 2020, trang 85 – 93.
Read more
##plugins.themes.academic_pro.article.sidebar##
Published
Jul 31, 2021
Download
How to Cite
Lê Xuân Hùng. “An Investigation into the Uniquely 2-List Colorable of Complete Split Graphs”. The University of Danang - Journal of Science and Technology, vol. 19, no. 7, July 2021, pp. 69-72, https://jst-ud.vn/jst-ud/article/view/7552.
