The chromatic number of a graph is the minimum number of colours used in a…
GATE · 2024 · CS · Set 1 · Computer Science & IT
The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let 𝐺 be any graph with 𝑛 vertices and chromatic number 𝑘. Which of the following statements is/are always TRUE?
- A.
𝐺 contains a complete subgraph with 𝑘 vertices
- B.
𝐺 contains an independent set of size at least 𝑛/ 𝑘
- C.
𝐺 contains at least 𝑘(𝑘 − 1)/2 edges
- D.
𝐺 contains a vertex of degree at least 𝑘
Attempted by 137 students.
Sign up free to check your answer
Sign up freeLoading lesson…