Colorings · Introduction

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

Recall that \(\Delta(G)\) is the maximum degree of \(G\), \(\omega(G)\) is the size of the largest clique, and \(\alpha(G)\) is the size of the largest (vertex) independent set.

Problem. Mark the true statements.

5 points

  1. For any graph \(G(V,E)\) it holds that \(\chi(G) \le |V|\).

  2. For any graph \(G(V,E)\) it holds that \(\chi(G) \le \Delta(G)\).

  3. For any graph \(G(V,E)\) it holds that \(\chi(G) \le \Delta(G)+1\).

  4. Let \(G=C_{n}\) be a cycle on \(n \in \mathbb{Z}_{\ge 3}\) vertices. Then \(\chi(G) = 2\).

  5. Let \(G=C_{n}\) be a cycle on \(n \in \mathbb{Z}_{\ge 3}\) vertices. Then \(\chi(G) \le 3\).

  6. Let \(G=C_{n}\) be a cycle on \(n \in \mathbb{Z}_{\ge 3}\) vertices and \(n\) is even. Then \(\chi(G) = 2\).

  7. Let \(G=C_{n}\) be a cycle on \(n \in \mathbb{Z}_{\ge 3}\) vertices and \(n\) is odd. Then \(\chi(G) = 3\).

  8. Let \(G=K_{n}\) be the complete graph on \(n\) vertices. Then \(\chi(G)=n\).

  9. For any graph \(G\) it holds that \(\chi(G)=\omega(G)\).

  10. For any graph \(G\) it holds that \(\chi(G)\ge \omega(G)\).

  11. For any graph \(G\) it holds that \(\chi(G)\le \omega(G)\).

  12. For any graph \(G\) it holds that \(\chi(G) \cdot \alpha(G) \le |V|\).

  13. For any graph \(G\) it holds that \(\chi(G) \cdot \alpha(G) \ge |V|\).