Is there a relationship between the clique of a graph and colouring of a graph?

4.3k Views Asked by At

Can one say that the minimum number of colours required to colour a graph (such that across any edge the two vertices have distinct colours) is lower bounded by the size of the maximum clique in the graph?

Is there anything more stronger known along these lines?

2

There are 2 best solutions below

4
On

The answer to your first question is yes. A graph is perfect if the chromatic number of each induced subgraph is eqaul to the size of the largest cliqu in the subgraph. There is a large literature on these but, unfortunately, most graphs are not perfect

On the other hand there are triangle-free graphs with arbitrarily large chromatic number, so nothing much can said in general.

0
On

Since the vertices in a clique are pairwise adjacent, the vertices in the clique must be assigned distinct colors. Thus, any proper coloring of the graph will require at least as many colors as the size of the largest clique in the graph.

The difference between the chromatic number and its lower bound (the clique number) can be made arbitrarily large - the Mycielskian gives an explicit construction.