TÍNH CHẤT CỦA ĐỒ THỊ TÁCH CỰC ĐẦY ĐỦ DUY NHẤT K-TÔ MÀU DANH SÁCH

Lê Xuân Hùng

Tóm tắt


Cho G là đồ thị có n đỉnh. Giả sử với mỗi đỉnh v của G, tồn tại một danh sách L(v) gồm k màu, sao cho có duy nhất một tô màu cho đồ thị G từ các danh sách màu này, khi đó G được gọi là đồ thị duy nhất k-tô màu danh sách. Đồ thị G được gọi là đồ thị tách cực nếu tồn tại phân hoạch V = I È K sao cho đồ thị con của G cảm sinh trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ thị đầy đủ. Khái niệm đồ thị tách cực được định nghĩa bởi Foldes và Hammer (1977). Các đồ thị này được nghiên cứu nhiều trong lý thuyết đồ thị. Bài báo này sẽ nghiên cứu tính chất của đồ thị tách cực đầy đủ khi nó là duy nhất k-tô màu danh sách.


Từ khóa


Đồ thị duy nhất k-tô màu danh sách; Đồ thị tách cực; Tô màu danh sách đỉnh; Tô màu đỉnh.

Toàn văn:

PDF

Các tài liệu tham khảo


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)

Các bài báo tham chiếu

  • Hiện tại không có bài báo tham chiếu.


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

Giấy phép URL: https://creativecommons.org/licenses/by-nc/4.0/
Văn phòng Tạp chí Đại học Đà Lạt
Nhà A25 - Số 1 Phù Đổng Thiên Vương, Đà Lạt, Lâm Đồng
Email: tapchikhoahoc@dlu.edu.vn - Điện thoại: (+84) 263 3 555 131

Creative Commons License
Trên nền tảng Open Journal Systems
Thực hiện bởi Khoa Công nghệ Thông tin