Sắc số cạnh của đồ thị tách cực với

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

Author

  • Lê Xuân Hùng*

Từ khóa:

đồ thị tách cực
tô màu cạnh
sắc số cạnh
đồ thị lớp một
đồ thị lớp hai

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 đủ. Chúng ta ký hiệu đồ thị tách cực đó là. 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,…. Trong bài báo này, một số điều kiện đủ để đồ thị tách cực thuộc Lớp một được chứng minh. Đặc biệt, chúng ta sẽ xác định sắc số cạnh của đồ thị tách cực với

và chứng minh được rằng sắc số cạnh của đồ thị là.

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] G. D. Birkhoff (1912), A determinant formula for the number of ways of coloring a map, Annals of Math, 14 (2), 42 -46.
    [4] J. A. Bondy and U. S. R. Murty (1976), Graph theory with applications, MacMillan.
    [5] B.-L. Chen, H.-L Fu, M.T. Ko (1995), Total chromatic number and chromatic index of split graphs, J. Combin. Math. Combin. Comput. 17, 137 – 146.
    [6] V. Chvatal and P.L. Hammer (1977), Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, pp. 145 – 162.
    [7] 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.
    [8] 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.
    [9] P. B. Henderson and Y. Zalcstein (1977), A graph-theoretic characterization of the class of synchroniring primitive, SIAM J. Comput. 6, 88-108.
    [10] 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.
    [11] A. J. W. Hilton and C. Zhao (1992), The chromatic index of a graph whose core has maximum degree two, Discrete Math. 101, 135 – 147.
    [12] A. J. W. Hilton and C. Zhao (1996), On the edge-colouring of graphs whose core has maximum degree two, J. Combin. Math. Combin. Comput. 21, 97 – 108.
    [13] 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.
    [14] 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, 2015
Download
PDF
Cách trích dẫn
Le Xuan Hung. “Sắc số cạnh của đồ thị tách cực với”. Tạp Chí Khoa học Và Công nghệ - Đại học Đà Nẵng, vol 9, số p.h 94, Tháng Chín 2015, tr 95-98, https://jst-ud.vn/jst-ud/article/view/2540.

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