Question

Is the chromatic number equal to the size of the largest possible complete subgraph of the graph(Cliques)?
Is there any relationship between chromatic number and cliques ?

Was it helpful?

Solution

In general, the answer to your questions are "No." and "No."

A graph whose maximum clique is equal to its chromatic number is called "perfect." It was a famous open problem to classify all perfect graphs which was recently solved: A graph is perfect if and only if it is a Berge graph.

It is widely believed that the chromatic number if a graph has chromatic number k, then it has the complete graph on k vertices as a minor. (Hadwiger's conjecture)

As for your second question, beyond the trivial clique number is less than or equal to the chromatic number, there is no strong connection. There are several conjectures relating clique number, chromatic number, and maximum degree in the case of triangle free graphs (see Reed '98)

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top