Câu hỏi 142
Giả sử $G$ là một đồ thị có số sắc độ bằng $n$. Giả sử tồn tại $k$ đồ thị $G_{1}, G_{2}, \ldots, G_{k}$ có cùng tập đỉnh với $G$ sao cho $G_{1} \cup G_{2} \cup \cdots \cup G_{k}=G$ và mỗi $G_{i}$ có số sắc độ không vượt quá $2$. Chứng minh rằng $k \geq \left\lceil \log_{2}(n) \right\rceil$, và chứng minh rằng luôn có thể tìm được một phân rã như vậy của $G$ thành $\left\lceil \log_{2}(n) \right\rceil$ đồ thị.