Câu hỏi 60
Trong bài toán này, $G$ biểu thị một đồ thị liên thông không có các cạnh song song (nhưng không nhất thiết phải là đồ thị phẳng) có phần bù $\overline{G}$. Đặt $V$ là tập các đỉnh, $E$ là tập các cạnh và $\Delta(G)$ hoặc $\Delta_G$ là bậc tối đa của các đỉnh. Xác định số màu $\chi(G)$ hoặc $\chi_G$ bằng
$$
\chi(G) = \chi_G = \min\{k : G \text{ có một } k\text{-tô màu}\}.
$$
Nói cách khác, $\chi(G)$ là số màu tối thiểu cần thiết để tô màu các đỉnh của $G$ sao cho không có hai đỉnh liền kề nào có cùng màu.
a. Chứng minh rằng nếu mọi đỉnh của $G$ đều có bậc 2 thì $V$ và $E$ tạo thành các góc và cạnh của một đa giác. Chúng được gọi là *đồ thị chu kỳ*.
b. Chứng minh rằng $\chi_G \le \Delta_G + 1$.
c. Hãy đưa ra hai loại ví dụ mà $\chi_G = \Delta_G + 1$.
d. Chứng minh rằng nếu $G$ không thuộc bất kỳ loại nào ở trên thì $\chi_G \le \Delta_G$.
e. Cho một ví dụ về $G$ sao cho $\chi(G) + \chi(\overline{G}) = \#V + 1$.
$$
\chi(G) = \chi_G = \min\{k : G \text{ có một } k\text{-tô màu}\}.
$$
Nói cách khác, $\chi(G)$ là số màu tối thiểu cần thiết để tô màu các đỉnh của $G$ sao cho không có hai đỉnh liền kề nào có cùng màu.
a. Chứng minh rằng nếu mọi đỉnh của $G$ đều có bậc 2 thì $V$ và $E$ tạo thành các góc và cạnh của một đa giác. Chúng được gọi là *đồ thị chu kỳ*.
b. Chứng minh rằng $\chi_G \le \Delta_G + 1$.
c. Hãy đưa ra hai loại ví dụ mà $\chi_G = \Delta_G + 1$.
d. Chứng minh rằng nếu $G$ không thuộc bất kỳ loại nào ở trên thì $\chi_G \le \Delta_G$.
e. Cho một ví dụ về $G$ sao cho $\chi(G) + \chi(\overline{G}) = \#V + 1$.