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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:3

Thêm vào BST

Báo xấu

17
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tất cả các đồ thị được nói tới trong bài báo này là những đơn đồ thị hữu hạn, vô hướng, không có khuyên và không có cạnh bội. Bài viết Tô màu danh sách của đồ thị tách cực 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 là xác định sắc số danh sách đối với đồ thị tách cực.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Tô màu danh sách của đồ thị tách cực

78 Lê Xuân Hùng TÔ MÀU DANH SÁCH CỦA ĐỒ THỊ TÁCH CỰC LIST COLORING OF SPLIT GRAPHS Lê Xuân Hùng Trường Đại học Tài nguyên và Môi trường Hà Nội; lxhung@hunre.edu.vn Tóm tắt - Đồ thị G  (V , E ) được gọi là đồ thị tách cực nếu tồn Abstract - A graph G  (V , E ) is called a split graph if there tại phân hoạch V  I  K sao cho đồ thị con của G cảm sinh exists a partition V  I  K so that the subgraphs of G induced trên I là đồ thị rỗng và đồ thị con của G cảm sinh trên K là đồ by I and K are empty and complete respectively. The notion of thị đầy đủ. Khái niệm đồ thị tách cực được định nghĩa vào năm split graphs was introduced in 1977 by S. Foldes and P.L.Hammer. 1977 bởi S. Foldes và P.L. Hammer. Các đồ thị này đã và đang These graphs have been paid much attention to because they have được nghiên cứu nhiều bởi vì chúng có liên quan các vấn đề tổ connection with packing and knapsack problems, with the matroid hợp và khoa học máy tính như bài toán đóng gói và xếp ba lô trong theory, with Boolean function, with the analysis of parallel quy hoạch nguyên, lý thuyết matroid, nghiên cứu hàm Boolean, processes in computer programming and with the task allocation in giải quyết việc xử lý song song trong các chương trình máy tính và distributed systems,…. One of the fundamentals in graph theory is xác định công việc trong hệ phân tán,… Một trong những vấn đề the problem of graph colorings. In this paper, we take a look at a chủ yếu trong lý thuyết đồ thị là bài toán tô màu đồ thị. Bài báo này relatively recent generalization of the concepts of coloring studied sẽ tổng quát hóa các khái niệm về tô màu đã được nghiên cứu từ so far.In particular we will determine list-chromatic number for split trước, đặc biệt là xác định sắc số danh sách đối với đồ thị tách cực. graphs. Từ khóa - đồ thị tách cực; tô màu đỉnh (tô màu); sắc số; tô màu Key words - Split graph; vertex coloring (coloring); chromatic danh sách đỉnh (tô màu danh sách); sắc số danh sách đỉnh (sắc số number; list coloring; list-chromatic number danh sách). 1. Đặt vấn đề Giả sử G là một đồ thị và  là một số nguyên dương. Tất cả các đồ thị được nói tới trong bài báo này là những Một ánh xạ f : E (G )  1, 2,...,  được gọi là  -tô màu ( đơn đồ thị hữu hạn, vô hướng, không có khuyên và không có cạnh bội. Nếu G là một đồ thị, thì V (G ) (hoặc V ) được  -coloring) của đồ thị G , nếu với mỗi cặp đỉnh u, v kề gọi là tập đỉnh và E (G ) (hoặc E ) được gọi là tập cạnh. Tập nhau trong G ta luôn có f (u )  f (v) . Số  nhỏ nhất để hợp tất cả các đỉnh là hàng xóm của tập con S  V (G ) được đồ thị G có  -tô màu được gọi là sắc số (chromatic ký hiệu là N G ( S ) (hoặc N(S)). Với mỗi đỉnh v  V (G ) , number) của đồ thị G và được ký hiệu là  (G) . Đồ thị G ta gọi N G ( v ) là bậc của đỉnh v, ký hiệu là deg G (v ) (hoặc được gọi là k-sắc nếu  (G)  k . deg(v)). Đồ thị con của G cảm sinh trên tập U  V (G ) Vấn đề tô màu danh sách được đề cập đến bởi R. Diestel (xem [4]). Cho đồ thị G  (V , E ) , với mỗi đỉnh v V ta được ký hiệu là G[U ] . Ngoài ra, một số khái niệm và ký hiệu khác được định nghĩa trong [1]. cho một danh sách các màu Sv . Nếu c là tô màu đỉnh của Đồ thị G  (V , E ) có cấp | V (G ) | n và cỡ | E (G ) | 0 G thỏa mãn c(v)  Sv với mọi v  V thì ta gọi c là tô màu được gọi là đồ thị rỗng, ký hiệu là On . danh sách đỉnh (hay tô màu danh sách) từ các danh sách Sv . Đồ thị G được gọi là k-tô màu danh sách (k-list- Đồ thị G  (V , E ) có cấp | V (G ) | n và cỡ n(n  1) colorable) nếu với mọi họ  S v vV thỏa mãn S v  k với | E (G ) | được gọi là đồ thị đầy đủ cấp n, ký hiệu mọi v V , ta luôn có một tô màu đỉnh từ các danh sách 2 là K n . Sv . Số nguyên dương k nhỏ nhất để đồ thị G là k-tô màu Đồ thị G  (V , E ) được gọi là đồ thị tách cực nếu tồn danh sách được gọi là sắc số danh sách (list-chromatic number) của G , ký hiệu là ch(G ) . tại một phân hoạch V  I  K sao cho đồ thị con G[I ] là đồ thị rỗng và đồ thị con G[ K ] là đồ thị đầy Dễ dàng nhận thấy rằng nếu G là đồ thị k-tô màu danh sách thì G cũng là đồ thị k-tô màu. Thật vậy, giả sử G  (V , E ) là đủ. Chúng ta ký hiệu đồ thị tách cực là S ( I  K , E ) . Khái đồ thị k-tô màu danh sách. Ta chỉ việc chọn S v  1, 2,..., k  niệm đồ thị tách cực được định nghĩa đầu tiên vào năm 1977 bởi Foldes và Hammer [5]. Các đồ thị này đã và đang với mọi v  V . Từ đó suy ra G là đồ thị k-tô màu. Như vậy, được nghiên cứu nhiều bởi vì chúng có liên quan nhiều đến với mọi đồ thị G ta luôn có ch(G)   (G) . các vấn đề về 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 [3], lý thuyết 2. Nội dung nghiên cứu matroid [6], nghiên cứu hàm Boolean [10], giải quyết việc 2.1. Một số kết quả liên quan xử lý song song trong các chương trình máy tính [7] và xác định công việc trong hệ phân tán [8],… Trước hết là các kết quả đã biết về sắc số của một số
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(106).2016 79 lớp đồ thị đặc biệt. danh sách màu là Sv1 , Sv2 ,..., Svn sao cho S vi  3 với mọi Bổ đề 1 ([1]). Nếu P là một đường không tầm thường i  1, 2,..., n . Gọi f là tô màu đỉnh của C thỏa mãn thì  ( P)  2 . f  v1   S v1 , f  v2   Sv2 \  f  v1  ,..., Bổ đề 2 ([1]). Giả sử C là một chu trình với V (C )  n  3 . f  vn 1   S vn1 \  f  vn  2  , Khi đó f  vn   S vn \  f  vn 1  , f  v1 . (i) Nếu n lẻ thì  (C )  3 ; Khi đó, rõ ràng f là 3-tô màu danh sách của C , hay (ii) Nếu n chẵn thì  (C )  2 . ch(C )  3 . Suy ra điều phải chứng minh. Bổ đề 3 ([2]). Đồ thị đầy đủ K n có (ii) Bây giờ ta chứng minh mệnh đề cho trường hợp n chẵn.  Kn   n . Theo Bổ đề 2 ta có  (C )  2 , do đó ch(C )  2 . Ta cần Tiếp theo là một kết quả về sắc số của đồ thị tách cực. phải chứng minh ch(C )  2 . Định lý 4 ([9]). Giả sử G  S ( I  K , E ) là đồ thị tách Giả sử C  v1v2 ...vn v1 và v1 , v2 ,..., vn lần lượt có các cực với K  n và danh sách màu là Sv1 , Sv2 ,..., Svn sao cho S vi  2 với mọi k  max deg(u ) | u  I  . i  1, 2,..., n . Giả sử  thuộc một trong các tập Khi đó Sv1 , Sv2 ,..., Svn . Ta xét hai trường hợp sau. (i)  (G)  n khi và chỉ khi k < n; Trường hợp 1:   Svi với mọi i  1, 2,..., n . (ii)  (G )  n  1 khi và chỉ khi k = n. Giả sử S vi   , ti  với mọi i  1, 2,..., n . Xét tô màu f 2.2. Kết quả chính của C thỏa mãn Trước hết ta sẽ phát biểu và chứng minh các kết quả về f  vi    nếu i lẻ, f  vi   ti nếu i chẵn. sắc số danh sách của một số lớp đồ thị đặc biệt. Mệnh đề 5. Nếu P là một đường không tầm thường thì Khi đó f cũng là 2-tô màu danh sách của C . ch( P)  2 . Trường hợp 2: Tồn tại i  2, 3,..., n sao cho   Svi Chứng minh. Giả sử P  v1v2 ...vn , n  2 . Theo Bổ đề 1 và   Svi1 . ta có  ( P)  2 . Do đó ch( P)  2 . Bây giờ ta sẽ chứng Không mất tính tổng quát ta giả sử   S vn và   S vn1 minh ch( P)  2 . . Gọi g là tô màu của C thỏa mãn Giả sử các đỉnh v1 , v2 ,..., vn lần lượt có các danh sách g  v1   Sv1 \   , g  v2   S v2 \  g  v1  ,..., màu là Sv1 , Sv2 ,..., Svn sao cho Svi  2 với mọi i  1, 2,..., n Rõ ràng g g  vn 1   S vn1 \  g  vn  2  , g  vn    . . Giả sử f là tô màu đỉnh của P thỏa mãn là 2-tô màu danh sách của C . f  v1   S v1 , f  v2   Sv2 \  f  v1  ,..., Như vậy, trong cả hai trường hợp ta đều chứng minh f  vn   S vn \  f  vn 1  . được tồn tại 2-tô màu danh sách của C , hay ch(C )  2 . Từ đó suy ra điều phải chứng minh. ■ Do đó, f là 2-tô màu danh sách của P . Suy ra Mệnh đề 7. Đồ thị đầy đủ K n có ch  K n   n . ch( P)  2 và ta có điều phải chứng minh. ■ Chứng minh. Theo Bổ đề 3 ta có   K n   n . Do đó Mệnh đề 6. Giả sử C là một chu trình với ch  K n   n . Ta tiếp tục phải chứng minh ch  K n   n . V (C )  n  3 . Giả sử đồ thị đầy đủ K n có các đỉnh là v1 , v2 ,..., vn và Khi đó (i) Nếu n lẻ thì ch(C )  3 ; S vi là danh sách màu của đỉnh vi sao cho S vi  n với mọi i  1, 2,..., n . Giả sử f là tô màu đỉnh của K n thỏa mãn (ii) Nếu n chẵn thì ch(C )  2 . Chứng minh. (i) Giả sử n lẻ. Theo Bổ đề 2 ta có f  v1   Sv1 , f  v2   Sv2 \  f  v1  ,...,  (C )  3 . Do đó ch(C )  3 . Ta sẽ chứng minh f  vn   Svn \  f  v1  , f  v2  ,..., f  vn 1 . ch(C )  3 . Khi đó f cũng là n-tô màu danh sách của đồ thị K n , Giả sử C  v1v2 ...vn v1 và v1 , v2 ,..., vn lần lượt có các do đó ch  K n   n . Suy ra điều phải chứng minh. ■
80 Lê Xuân Hùng Cuối cùng ta sẽ phát biểu và chứng minh một kết quả f là tô màu đỉnh của G thỏa mãn về sắc số danh sách của đồ thị tách cực. f  vi   g  vi  với mọi i  1, 2,..., n ; Định lý 8. Giả sử G  S ( I  K , E ) là đồ thị tách cực với K  n và f  ui   S ui \ g  N  ui   với mọi i  1, 2,..., m. k  max deg(u ) | u  I  . Rõ ràng f là (n + 1)-tô màu danh sách của đồ thị G , Khi đó do đó ch(G )  n  1 . Suy ra điều phải chứng minh. ■ (i) ch(G )  n khi và chỉ khi k < n; 3. Kết luận (ii) ch(G )  n  1 khi và chỉ khi k = n. Trong lý thuyết đồ thị, đã có nhiều kết quả nghiên cứu về bài toán tô màu. Đặc biệt, trong [4] có đề cập đến bài Chứng minh. (i) Giả sử ch(G )  n . Nếu k = n thì G chứa toán tô màu danh sách của đồ thị (bao gồm cả tô màu danh đồ thị đầy đủ cấp n + 1. Từ Mệnh đề 7 ta suy ra ch(G )  n  1 sách đỉnh và tô màu danh sách cạnh). Đây có thể coi là một , điều này trái với giả thiết. Vậy ta phải có k < n. tổng quát hóa của bài toán tô màu đồ thị. Với việc tiếp cận vấn đề tô màu danh sách đỉnh, bài báo đã giải quyết xong Bây giờ giả sử k < n. Theo Định lý 4 ta có  (G )  n , bài toán tô màu danh sách đỉnh đối với một số lớp đồ thị, do đó ch(G )  n . Ta sẽ chứng minh ch(G )  n . Giả sử trong đó nổi bật là lớp đồ thị tách cực, đây là những kết quả I  u1 , u2 ,..., um  , lần đầu tiên được phát biểu và chứng minh, góp phần làm phong phú thêm các kết quả nghiên cứu về bài toán tô màu K  v1 , v2 ,..., vn  . nói chung và bài toán tô màu danh sách đỉnh nói riêng. Từ và Su1 , Su2 ,..., S um , S v1 , S v2 ,..., S vn lần lượt là danh sách màu những kết quả này, trong tương lai hy vọng sẽ tiếp tục có những kết quả sâu sắc hơn về bài toán tô màu danh sách của các đỉnh u1 , u2 ,..., um , v1 , v2 ,..., vn sao cho nói riêng và bài toán tô màu nói chung. Su1  Su2  ...  Sum  Sv1  S v2  ...  S vn  n. TÀI LIỆU THAM KHẢO Theo Mệnh đề 7, tồn tại n-tô màu danh sách g của đồ thị [1] M. Behazad and G. Chartrand (1971), Introduction to the Theory of G  K  với các danh sách màu là S v1 , S v2 ,..., S vn . Gọi f là graphs, Allyn and Bacon, Boston. tô màu đỉnh của G thỏa mãn [2] M. Behazad and G. Chartrand and J. Cooper (1967), The coloring numbers of complete graphs, J. London Math. Soc. 42, 226 – 228. f  vi   g  vi  với mọi i  1, 2,..., n ; [3] V. Chvatal and P.L. Hammer (1977), Aggregation of inequalities in integer programming, Ann. Discrete Math. 1, pp. 145 – 162. f  ui   S ui \ g  N  ui   với mọi i  1, 2,..., m. [4] R. Diestel (2000), Graph Theory, Springer – Verlag, New Your. [5] S. Foldes and P.L. Hammer (1977), Split graphs, In: Proceeding of Rõ ràng f là n-tô màu danh sách của đồ thị G , do đó the Eighth Southeastern Conference on Combinatorics, Graph ch(G )  n . Suy ra điều phải chứng minh. Theory and Computing (Louisiana State University, Baton Rouge, LA, 1977), Congressus Numerantium, vol. XIX, Utilitas (ii) Giả sử ch(G )  n  1 . Nếu k < n thì theo (i) ta có Mathematics, Winnipeg, Man., pp. 311 – 315. [6] S. Foldes and P.L. Hammer (1978), On a class of matroid-producing ch(G )  n , điều này trái với giả thiết. Do đó ta phải có k = n. graphs, In: Combinatorics (Proceeding of the Filth Hungarian Colloquium, Kesrthely, 1976), vol. 1, Colloquium Mathematical Giả sử k = n. Khi đó G chứa đồ thị con đầy đủ cấp n Society, Jano’s Bolyai, vol. 18, North-Holland, Amsterdam, New + 1 nên theo Định lý 4 ta có  (G )  n  1 . Suy ra York, pp. 331 - 352. ch(G )  n  1 . Ta sẽ chứng minh ch(G )  n  1 . Giả sử [7] P. B. Henderson and Y. Zalcstein (1977), A graph-theoretic characterization of the PVchunk class of synchroniring primitive, I  u1 , u2 ,..., um  , SIAM J. Comput. 6, 88-108. K  v1 , v2 ,..., vn  . [8] A. Hesham H. And El-R. Hesham (1993), Task allocation in distributed systems: a split graph model, J. Combin. Math. Combin. và Su1 , Su2 ,..., S um , S v1 , S v2 ,..., S vn lần lượt là danh sách màu Comput. 14, 15-32. [9] Lê Xuân Hùng (2014), “Sắc số, đa thức tô màu và tính duy nhất tô của các đỉnh u1 , u2 ,..., um , v1 , v2 ,..., vn sao cho 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. S u1  Su2  ...  Sum  S v1  S v2  ...  Svn  n  1. [10] U. N. Peled (1975), Regular Boolean functions and their polytope, Chapter VI, PH. D. Thesis, Univ. Of Waterloo, Dept. Combin. And Theo Mệnh đề 7, tồn tại (n + 1)-tô màu danh sách g của Optimization. đồ thị G  K  với các danh sách màu là S v1 , S v2 ,..., S vn . Gọi (BBT nhận bài: 28/07/2016, phản biện xong: 07/09/2016)