How to demonstrate that χ(G)=omega(G), G is a bipartite graph If G is a bipartite graph then χ(G)=omega(G)?

Gauge Roach

Gauge Roach

Answered question

2022-08-07

How to demonstrate that χ ( G ¯ ) = ω ( G ¯ ), G is a bipartite graph
If G is a bipartite graph then χ ( G ¯ ) = ω ( G ¯ )?

Answer & Explanation

Irene Simon

Irene Simon

Beginner2022-08-08Added 16 answers

Suppose we have a partition of the complement of G into two cliques X and Y where | X | = n is maximal. We prove the result by induction on | Y | . Assume X is colored with c 1 , c 2 , , c n distinct colors. If Y is empty, then we are done. Otherwise assume we have colored X ( Y { y } ) properly. We want to choose a color for y. If y is not adjacent to some unused color, then choose that color.
Assume therefore that y is adjacent to all unused colors. If every other vertex in Y were adjacent to all of these | X | | Y | + 1 colors as well, then we would have a clique of size | X | + 1, contradicting maximality. Thus let y be a vertex with color c and let c be an unused color that y is not adjacent to. Let c be a color in X that y is not adjacent to and let y be the vertex in Y with color c . Then color y with c , y with c, and y with c . This is a proper coloring, and the result follows by induction.

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?