Tô màu danh sách của đồ thị tách cực

##plugins.themes.academic_pro.article.main##

Author

  • Lê Xuân Hùng*

Từ khóa:

đồ thị tách cực
tô màu đỉnh (tô màu)
sắc số
tô màu danh sách đỉnh (tô màu danh sách)
sắc số danh sách đỉnh (sắc số danh sách)

Tóm tắt

Đồ thị được gọi là đồ thị tách cực nếu tồn tại phân hoạch sao cho đồ thị con của cảm sinh trên là đồ thị rỗng và đồ thị con của cảm sinh trên là đồ thị đầy đủ. Khái niệm đồ thị tách cực được định nghĩa vào năm 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này đã và đang được nghiên cứu nhiều bởi vì chúng có liên quan các vấn đề tổ hợp và khoa học máy tính như bài toán đóng gói và xếp ba lô trong quy hoạch nguyên, lý thuyết matroid, nghiên cứu hàm Boolean, giải quyết việc xử lý song song trong các chương trình máy tính và xác định công việc trong hệ phân tán,….Một trong những vấn đề chủ yếu trong lý thuyết đồ thị là bài toán tô màu đồ thị. Trong bài báo này, chúng ta sẽ tổng quát hóa các khái niệm về tô màu đã được nghiên cứu từ trước, đặc biệt chúng ta sẽ xác định sắc số danh sách đối với đồ thị tách cực.

Tài liệu tham khảo

    [1] M. Behazad and G. Chartrand (1971), Introduction to the Theory of graphs, Allyn and Bacon, Boston.
    [2] M. Behazad and G. Chartrand and J. Cooper (1967), The coloring numbers of complete graphs, J. London Math. Soc. 42, 226 – 228.
    [3] V. Chvatal and P.L. Hammer (1977), Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, pp. 145 – 162.
    [4] R. Diestel (2000), Graph Theory, Springer – Verlag, New Your.
    [5] S. Foldes and P.L. Hammer (1977), 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., pp. 311 – 315.
    [6] S. Foldes and P.L. Hammer (1978), 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, pp. 331 - 352.
    [7] P. B. Henderson and Y. Zalcstein (1977), A graph-theoretic characterization of the class of synchroniring primitive, SIAM J. Comput. 6, 88-108.
    [8] A. Hesham H. And El-R. Hesham (1993), Task allocation in distributed systems: a split graph model, J. Combin. Math. Combin. Comput. 14, 15-32.
    [9] Lê Xuân Hùng (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, Trường Đại học Sư phạm, ĐHĐN, 13(04), 23 – 27.
    [10] U. N. Peled (1975), Regular Boolean functions and their polytope, Chapter VI, PH. D. Thesis, Univ. Of Waterloo, Dept. Combin. And Optimization.
Xem thêm

##plugins.themes.academic_pro.article.sidebar##

Đã Xuất bản

Sep 30, 2016
Download
PDF
Cách trích dẫn
Le Xuan Hung. “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, vol 9, số p.h 106, Tháng Chín 2016, tr 78-80, https://jst-ud.vn/jst-ud/article/view/1477.

##plugins.themes.academic_pro.article.details##