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

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.