Prove χ(G)χ(G)>=n for chromatic number of graph and its complement Let us denote by χ(G) the chromatic number, which is the smallest number of colours needed to colour the graph G with n vertices. Let G be the complement of G. Show that (a) χ(G)+χ(G)<=n+1 (b) χ(G)χ(G)>=n I was able to prove (a) using induction. Any hints on proving (b)?

Damien Horton

Damien Horton

Answered question

2022-07-16

Prove χ ( G ) χ ( G ¯ ) n for chromatic number of graph and its complement
Let us denote by χ(G) the chromatic number, which is the smallest number of colours needed to colour the graph G with n vertices. Let G ¯ be the complement of G. Show that
χ ( G ) + χ ( G ¯ ) n + 1
χ ( G ) χ ( G ¯ ) n
I was able to prove (a) using induction. Any hints on proving (b)?

Answer & Explanation

repotasonwf

repotasonwf

Beginner2022-07-17Added 12 answers

Hint: consider the graph with:
vertex set G × G
edges between ( v , w ) and (x,y) iff there is an edge v to x in G or there is an edge w to y in G ¯
colouring C ( v , w ) = ( c ( v ) , c ¯ ( w ) ) where c is the colouring of G and c ¯ is the colouring of G ¯ .
If you're wondering where I got this from, I just tried to find a graph that had the information of G in it and was coloured by χ ( G ) χ ( G ¯ ) colours.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?