Tô màu đồ thị

Trong Lý thuyết đồ thị, tô màu đồ thị (tiếng Anh: "graph coloring") là trường hợp đặc biệt của gán nhãn đồ thị, mà trong đó mỗi đỉnh hay mỗi cạnh hay mỗi miền của đồ thị có thể được gán bởi một màu hay một tập hợp các màu nào đó. Tô màu đồ thị có thể là:
Sắc số (tiếng Anh: "chromatic number") của một đồ thị là số màu ít nhất để tô các đỉnh.
Sắc số của đồ thị "G" được ký hiệu là χ("G").
Số màu cạnh (tiếng Anh: "chromatic index") của một đồ thị là số màu ít nhất dùng để tô các cạnh. Số màu cạnh của đồ thị "G" được ký hiệu là χ'("G").
Số màu cạnh của đồ thị "G" bất kì bằng sắc số của đồ thị đường L("(G)") của đồ thị đó:
do đó việc nghiên cứu tô màu cạnh của "G" tương đương với nghiên cứu tô màu đỉnh của L("G").
Các định lý và tính chất.
Các giá trị giới hạn của sắc số.
Rõ ràng sắc số của một đồ thị sẽ không vượt quá số đỉnh của nó (bậc của đồ thị):
Nếu "G" có clique kích thước "k" thì cần ít nhất "k" màu để tô màu đỉnh cho clique này (xem thêm bài về đồ thị đầy đủ), như vậy sắc số của một đồ thị sẽ không nhỏ hơn "chỉ số clique" của đồ thị đó:
Nếu đồ thị đơn "G" có bậc cực đại bằng Δ(G) thì sắc số của nó không vượt quá Δ(G)+1.
Tổng quát hơn là định lý Brook, định lý khẳng định rằng:
Nếu đồ thị "G" có "m" cạnh thì sắc số của nó thỏa mãn:
Một số định lý liên quan của sắc số.
Định lý 1.
Bất cứ chu trình độ dài lẻ nào cũng đều có sắc số bằng 3
Chứng minh:
Giả sử chu trình có độ dài là formula_19 ta chứng minh theo số formula_20
Nối formula_26 với formula_28 ta được một chu trình formula_24'có độ dài formula_34.
Theo giả thuyết quy nạp chu trình formula_24' có sắc số bằng 3.
Lấy màu của formula_26 tô cho formula_29 còn màu của formula_28 tô cho formula_30.
Chu trình formula_24 được tô màu mà không thêm màu mới vào.
Vậy chu trình formula_24 có sắc số bằng 3
Định lý 2.
Đồ thị đầy đủ n đỉnh Kn có sắc số bằng n
Một số tiêu chuẩn đơn giản để kiểm tra xem 1 đồ thị có hai sắc số hay không:
Chứng minh:
Chọn 1 đỉnh a nào đó bất kì trong đồ thị
Đặt formula_42 (m: số màu)
Với formula_43 formula_44 formula_45 Ta ký hiệu formula_46là độ dài đường đi vô hướng ngắn nhất nối formula_45 vớiformula_43
Đặt formula_49 mod 2
"Ta sẽ chứng minh m là hàm màu của G"
Giả sử formula_50 kề nhau
Chu trình đơn formula_57 có độ dài formula_58phải là một số chẵn
Vậy thì formula_59 là một số lẻ formula_22 formula_61 khác nhau tính chẵn lẻ
formula_62formula_63 formula_44 formula_65
Hàm tô màu m có hai giá trị, vậy sắc số ≤ 2. G có ít nhất một cạnh nên sắc số của nó bằng 2
Từ định lý trên ta có hệ quả sau: Tất cả các chu trình độ dài chẵn đều có sắc số bằng 2.
Định lý 3.
Phát biểu: Nếu G có chứa 1 đồ thị con đẳng cấu với Kn thì formula_66.
Chứng minh: Hiển nhiên
Các giá trị giới hạn của số màu cạnh.
Định lý 1.
Xét đồ thị formula_67 có hai đỉnh bất kì liền kề và formula_67 có các khuyên. "n" là số đỉnh của formula_67.
Đánh số các đỉnh của formula_67 là formula_71.
Chỉ cần chứng minh formula_67 có thể tô màu các cạnh bởi "n" màu thì suy ra đồ thị đơn "G" bất kì có số đỉnh không vượt quá "n" đều có thể tô các cạnh bởi "n" màu.
Ký hiệu các màu là formula_73.
Khi đó ta có cách tô màu cho formula_67 như sau.
Ma trận dưới đây biểu thị cách tô màu, trong đó:
Định lý König khẳng định rằng đối với đồ thị hai phía "G", số màu cạnh của nó bằng bậc cực đại của nó: formula_77.
Định lý Vizing khẳng định rằng, nếu đồ thị đơn "G" có bậc cực đại bằng formula_78 thì số màu cạnh của nó bằng formula_78 hoặc formula_80.
Đa thức màu.
Xem bài đa thức màu.
Sắc số và số màu cạnh của một số đồ thị cơ bản.
Khái niệm sắc số liên quan đến bài toán tô màu như sau: 
Hãy tô màu các đỉnh của đồ thị đã cho, sao cho 2 đỉnh kề phải được tô bằng hai màu khác nhau
Đồ thị hai phía.
Đồ thị hai phía đầy đủ formula_81 có sắc số bằng 2: χ(formula_82)=2. Mở rộng: một đồ thị hai phía bất kì có sắc số không vượt quá 2.
Ví dụ minh họa là các đỉnh của đồ thị formula_82 có thể được tô bởi hai màu xanh và đỏ.
Đồ thị chu trình.
Đồ thị chu trình formula_84 có sắc số bằng:
Số màu cạnh:
Đồ thị bánh xe.
Đồ thị bánh xe formula_4 ("n"≥4) có sắc số bằng:
Số màu cạnh ("n"≥3):
Đồ thị đầy đủ.
Đồ thị đầy đủ formula_3 có sắc số bằng:
Số màu cạnh:
Đánh số các đỉnh của formula_3 là formula_71.
Do mỗi đỉnh của formula_3 có bậc bằng "n"-1, nên số màu cạnh của nó không nhỏ hơn "n"-1, do đó χ'(formula_3) bằng "n" hoặc "n"-1.
Chứng minh χ'(formula_3)="n"-1 với "n" chẵn:
Chứng minh χ'(formula_3)="n" với "n" lẻ:
Đồ thị siêu khối.
Đồ thị siêu khối formula_114 có sắc số bằng 2, vì bản thân nó là đồ thị phân đôi.
Ứng dụng.
Tô màu bản đồ.
Trên các bản đồ, các miền khác nhau (miền ở đây được hiểu là các quốc gia trên bản đồ thế giới hay các tỉnh trong một bản đồ hành chính quốc gia) được tô màu sao cho 2 miền có chung biên giới không trùng màu nhau. Đối với bản đồ có nhiều miền, nếu ta dùng một số lượng lớn màu thì sẽ rất khó phân biệt các miền có màu gần giống nhau, vì thế người ta chỉ dùng một số lượng màu nhất định để tô màu bản đồ. Một bài toán được đặt ra là: có thể dùng ít nhất bao nhiêu màu để tô màu một bản đồ sao cho các miền kề nhau không cùng một màu (tr.593).
Bài toán này dẫn đến định lý bốn màu nổi tiếng và định lý năm màu.
Các dạng bài toán tô màu bản đồ có thể áp dụng Thuật toán tô màu Greedy để tìm ra số màu ít nhất để tô cho các miền trên bản đồ.