Mỗi bản đồ trên mặt phẳng có thể biểu diễn bằng một đồ thị, trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh; các cạnh nối hai đỉnh, nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Rõ ràng mọi bản đồ trên mặt phẳng đều có đồ thị đối ngẫu phẳng. Bài toán tô màu các miền của bản đồ là tương đương với bài toán tô màu các đỉnh của đồ. | ĐÒ THỊ PHẲNG VÀ TÔ MÀU ĐÒ THỊ - PHẦN 2 . Tô màu đồ thị Mỗi bản đồ trên mặt phang có thể biểu diễn bằng một đồ thị trong đó mỗi miền của bản đồ được biểu diễn bằng một đỉnh các cạnh nối hai đỉnh nếu các miền được biểu diễn bằng hai đỉnh này là kề nhau. Đồ thị nhận được bằng cách này gọi là đồ thị đối ngẫu của bản đồ đang xét. Rõ ràng mọi bản đồ trên mặt phăng đều có đồ thị đối ngẫu phăng. Bài toán tô màu các miền của bản đồ là tương đương với bài toán tô màu các đỉnh của đồ thị đối ngẫu sao cho không có hai đỉnh liền kề nhau có cùng một màu mà ta gọi là tô màu đúng các đỉnh của đồ thị. Số màu ít nhất cần dùng để tô màu đúng đồ thị G được gọi là sắc số của đồ thị G và ký hiệu là x G . Thí dụ 6 Ta thấy rằng 4 đỉnh b d g e đôi một kề nhau nên phải được tô bằng 4 màu khác nhau. Do đó màu G như sau X G 4. Ngoài ra có thể dùng 4 màu đánh số 1 2 3 4 để tô CD CD Như vậy x G 4. . Mệnh đê Nếu đồ thị G chứa một đồ thị con đồng phôi với đồ thị đầy đủ Kn thì x G n. Chứng minh Gọi H là đồ thị con của G đồng phôi với Kn thì x H n. Do đó X G n. . Mệnh đê Nếu đơn đồ thị G không chứa chu trình độ dài lẻ thì x G 2. Chứng minh Không mất tính chất tổng quát có thể giả sử G liên thông. Cố định đỉnh u của G và tô nó bằng màu 0 trong hai màu 0 và 1. Với mỗi đỉnh v của G tồn tại một đường đi từ u đến v nếu đường này có độ dài chẵn thì tô màu 0 cho v nếu đường này có độ dài lẻ thì tô màu 1 cho v. Nếu có hai đường đi mang tính chẵn lẻ khác nhau cùng nối u với v thì dễ thấy rằng G phải chứa ít nhất một chu trình độ dài lẻ. Điều mâu thuẫn này cho biết hai màu 0 và 1 tô đúng đồ thị G. . Mệnh đê Với mỗi số nguyên dương n tồn tại một đồ thị không chứa K3 và có sắc số bằng n. Chứng minh Ta chứng minh mệnh đề bằng quy nạp theo n. Trường hợp n 1 là hiển nhiên. Giả sử ta có đồ thị Gn với kn đỉnh không chứa K3 và có sắc số là n. Ta xây dựng đồ thị Gn 1 gồm n bản sao của Gn và thêm knn đỉnh mới theo cách sau mỗi bộ thứ tự vi v2 . vn với vi thuộc bản sao Gn thứ i sẽ tương ứng với một
