Date Log
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
Corresponding Author(s) : Lê Xuân Hùng
Tạp chí Khoa học Xã hội, Nhân văn và Giáo dục,
T. 4 S. 4 (2014): TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC
Tóm tắt
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ị. Đặc biệt là xác định sắc số, đa thức tô màu và nghiên cứu tính duy nhất tô màu của đồ thị. Trong bài báo này chúng ta sẽ xác định sắc số, đa thức tô màu và nghiên cứu tính duy nhất tô màu của đồ thị tách cực.
Từ khóa
Tải về trích dẫn
Endnote/Zotero/Mendeley (RIS)BibTeX
-
[1] M. Behazad and G. Chartrand (1971), Introduction to the Theory of graphs, Allyn and Bacon, Boston.
[2] G. D. Birkhoff (1912), A determinant formula for the number of ways of coloring a map, Annals of Math, 14 (2), 42 -46.
[3] J. A. Bondy and U. S. R. Murty (1976), Graph theory with applications, MacMillan.
[4] 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.
[5] V. Chvatal and P.L. Hammer (1977), Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, pp. 145 – 162.
[6] 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.
[7] 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.
[8] P. B. Henderson and Y. Zalcstein (1977), A graph-theoretic characterization of the class of synchroniring primitive, SIAM J. Comput. 6, 88-108.
[9] 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.
[10] K. M. Koh and K. L. Teo (1990), The search for chromatically unique graphs, Graphs Combin. 6, 259-285.
[11] K. M. Koh and K. L. Teo (1997), The search for chromatically unique graphs II, Discrete Math. 172, 59-78.
[12] U. N. Peled (1975), Regular Boolean functions and their polytope, Chapter VI, PH. D. Thesis, Univ. Of Waterloo, Dept. Combin. And Optimization.
[13] R. C. Read (1968), An introduction to chromatic polynomials, J. Combin. Theory 4, 52-71.
[14] R. C. Read (1987), Connectivity and chromatic uniqueness, Ars Combin. 23, 209-218.