aligass2004yi

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\left(G\right)={V}_{1}\bigsqcup {V}_{2}$ such that $\chi \left(G\left[{V}_{1}\right]\right)+\chi \left(G\left[{V}_{2}\right]\right)>\chi \left(G\right)$
I managed to show that we can assume that every vertex x with non-full degree has degree atleast $\chi \left(G\right)-1$ (otherwise, we may take ${V}_{1}=\left\{x\right\}$ 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.

nuvolor8

Expert

Step 1
Let v be a vertex with non-full degree. Take ${V}_{1}=\left\{v\right\}\cup N\left(v\right)$ and ${V}_{2}=V\left(G\right)\setminus {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 $\chi \left(G\right)\le \chi \left(G\left[{V}_{1}\right]\right)+\chi \left(G\left[{V}_{2}\right]\right)-1$ and we are done.

Do you have a similar question?