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

Chromatic number, chromatic polynomials and chromatic uniqueness of split graphs
Tác giả: TS. Lê Xuân Hùng,

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: Đồ thị tách cực; tô màu đỉnh (tô màu) ; sắc số; đa thức tô màu; đồ thị duy nhất tô màu.

Abstract:

The notion of split graphs was introduced in 1977 by S. Foldes and P.L. Hammer. These graphs have been extensively studied because they are in connection with combinatorial problems and computer science such as packing and knapsack problems, the matroid theory, Boolean function, the analysis of parallel processes of computer programs and the task allocation of distributed systems… One of the fundamental matters in graph theory is the graph coloring, especially the determination of chromatic number, chromatic polynomials, and the uniqueness of graph coloring. This paper determines the chromatic number, chromatic polynomials and chromatical uniqueness of split graphs.

Keywords: split graph; vertex colorings (colorings); chromatic number; chromatic polynomials; chromatically unique graph.

Các bài báo khác của tác giả được đăng trên tạp chí

Số thứ tự Bài báo Tạp chí Trang Ngày đăng