Construct partition such that sum of chromatic numbers is greater than chromatic number of graphShow...

aligass2004yi

aligass2004yi

Answered

2022-07-01

Construct partition such that sum of chromatic numbers is greater than chromatic number of graph
Show that for any undirected non-complete graph G there is a partition V ( G ) = V 1 V 2 such that χ ( G [ V 1 ] ) + χ ( G [ V 2 ] ) > χ ( G )
I managed to show that we can assume that every vertex x with non-full degree has degree atleast χ ( G ) 1 (otherwise, we may take V 1 = { x } and consider its neighbors), but then I get stuck. I also considered doing induction by taking the "almost-complete" non-complete graph (i.e. a complete graph with one edge removed) and removing edges, but I'm not sure what to do in the induction step. Any help would be appreciated.

Answer & Explanation

nuvolor8

nuvolor8

Expert

2022-07-02Added 32 answers

Step 1
Let v be a vertex with non-full degree. Take V 1 = { v } N ( v ) and V 2 = V ( G ) V 1 . Now notice that if we can color V 1 with k 1 colors and V 2 with k 2 colors then we can color G with k 1 + k 2 1 colors by coloring v with one of the colors of V 2 (this comes from the fact that v cannot have the same color with any of the other vertices in V 1 ).
Step 2
This gives us that χ ( G ) χ ( G [ V 1 ] ) + χ ( G [ V 2 ] ) 1 and we are done.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get your answer.

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

Didn't find what you were looking for?