Câu hỏi 87
Với một đồ thị $G$, đặt
$$\begin{aligned}
\chi_G&=\min\{k:G\text{ có một cách tô màu bằng }k\text{ màu}\},\\
\Delta_G&=\max\{\text{bậc của các đỉnh của }G\}.
\end{aligned}$$
a. Chứng minh rằng với mọi đồ thị đơn liên thông $G$, ta có $\chi_G\leq\Delta_G+1$.
b. Đồ thị chính quy là đồ thị mà mọi đỉnh đều có cùng bậc. Chứng minh rằng nếu đồ thị đơn liên thông $G$ không chính quy thì $\chi_G\leq\Delta_G$.
$$\begin{aligned}
\chi_G&=\min\{k:G\text{ có một cách tô màu bằng }k\text{ màu}\},\\
\Delta_G&=\max\{\text{bậc của các đỉnh của }G\}.
\end{aligned}$$
a. Chứng minh rằng với mọi đồ thị đơn liên thông $G$, ta có $\chi_G\leq\Delta_G+1$.
b. Đồ thị chính quy là đồ thị mà mọi đỉnh đều có cùng bậc. Chứng minh rằng nếu đồ thị đơn liên thông $G$ không chính quy thì $\chi_G\leq\Delta_G$.