No, if all maximal cliques have size at least 3, you may take a graph coloring and unite two colors.
Fedor Petrov
- 108.9k
- 9
- 264
- 459