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

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 viết 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.
Nội dung trích xuất từ tài liệu:
Sắc số, đa thức tô màu và tính duy nhất tô màu của đồ thị tách cựcUED JOURNAL OF SOCIAL SCIENCES, HUMANITIES AND EDUCATION VOL.4, NO.4 (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 CHROMATIC NUMBER, CHROMATIC POLYNOMIALS AND CHROMATIC UNIQUENESS OF SPLIT GRAPHS Lê Xuân Hùng Trường Đại học Tài nguyên Hà Nội Email: lxhung@hunre.edu.vn 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 đónggó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 songtrong 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àucủ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 beenextensively studied because they are in connection with combinatorial problems and computer science such aspacking and knapsack problems, the matroid theory, Boolean function, the analysis of parallel processes of computerprograms and the task allocation of distributed systems… One of the fundamental matters in graph theory is the graphcoloring, especially the determination of chromatic number, chromatic polynomials, and the uniqueness of graphcoloring. This paper determines the chromatic number, chromatic polynomials and chromatical uniqueness of splitgraphs. Key words: split graph; vertex colorings (colorings); chromatic number; chromatic polynomials; chromaticallyunique graph.1. Giới thiệu trong [1]. Tất cả các đồ thị được nói tới trong bài báo Đồ thị G = (V , E ) được gọi là đồ thị táchnày là những đơn đồ thị hữu hạn, vô hướng, không cực nếu tồn tại một phân hoạch V = I  K saocó khuyên và không có cạnh bội. Nếu G là một cho đồ thị con G[I] là đồ thị rỗng và đồ thị conđồ thị, thì V(G) (hoặc V) được gọi là tập đỉnh và G[K] là đồ thị đầy đủ. Chúng ta ký hiệu đồ thị táchE(G) (hoặc E) được gọi là tập cạnh. Tập hợp tất cả cực là S ( I  K , E ) . Khái niệm đồ thị tách cựccác đỉnh là hàng xóm của tập con S  V (G) được được định nghĩa đầu tiên vào năm 1977 bởi Foldeský hiệu là N G (S ) (hoặc N(S)). Với mỗi đỉnh và Hammer [11]. Các đồ thị này đã và đang đượcv V (G) , ta gọi N G (v ) là bậc của đỉnh v, ký nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến các vấn đề về tổ hợp và khoa học máy tínhhiệu là degG (v) (hoặc deg(v)). Đồ thị con của G như bài toán đóng gói và xếp ba lô trong quycảm sinh trên tập U  V (G) được ký hiệu là hoạch nguyên [5], lý thuyết matroid [7], nghiênG[U ] . Đồ thị rỗng cấp n và đồ thị đầy đủ cấp n cứu hàm Boolean [12], giải quyết việc xử lý song song trong các chương trình máy tính [8] và xáclần lượt được ký hiệu là On và K n . Ngoài ra, một định công việc trong hệ phân tán [9],…số khái niệm và ký hiệu khác được định nghĩa Giả sử G là một đồ thị và  là một số 23TẠP CHÍ KHOA HỌC XÃ HỘI, NHÂN VĂN VÀ GIÁO DỤC TẬP 4, SỐ 4 (2014)nguyên dương. Một ánh xạ f : V (G) → 1,2,...,  giữa hai đỉnh bất kỳ của G đều tồn tại một đườngđược gọi là  -tô màu (  -coloring) của đồ thị G đi. Đồ thị G được gọi là k-liên thông ( k  2 ) nếunếu với mỗi cặp đỉnh u, v kề nhau trong G ta luôn hoặc G là đồ thị đầy đủ K k +1 , hoặc G có ít nhấtcó f (u )  f (v) . Số  nhỏ nhất để đồ thị G có k + 2 đỉnh và không có bất kỳ tập nào gồm k – 1 -tô màu được gọi là sắc số của đồ thị G và đỉnh tách được nó. Tiếp theo là một số kết quả đãđược ký hiệu là  (G) . Đồ thị G được gọi là k- biết về các đồ thị tương đương tô màu. Định lý 2 ([13]). Giả sử G và H là hai đồsắc nếu  (G) = k và được gọi là r-tới hạn nếu thị tương đương tô màu. Khi đó (G) = r và  ( H )   (G) với mọi H là đồ thị (i) V (G ) = V ( H ) ;con thực sự của G . Hai  -tô màu f và g của đồ thị G được (ii) E (G ) = E ( H ) ;gọi là khác nhau nếu tồn tại u V (G) sao cho (iii)  (G) =  ( H ) ; f (u)  g (u) . Ta ký hiệu P(G,  ) (hoặc P(G)) là (iv) G là liên thông khi và chỉ khi H làsố tất cả các  -tô màu khác nhau của đồ thị G . liên thông;Người ta đã chứng minh được rằng với mọi đồ thị (v) G là 2-liên thông khi và chỉ khi H làG, P(G,  ) là một đa thức của  . Đa thức này 2-liên thông. Đồ thị liên thông  -duy nhất H được gọiđược gọi là đa thức tô màu của G. Khá ...