Construct partition such that sum of chromatic numbers is greater than chromatic number of graphShow 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 ] ) &gt; χ ( 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.

Question

Construct partition such that sum of chromatic numbers is greater than chromatic number of graphShow 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    ]  )  &amp;gt;  χ  (  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 &quot;almost-complete&quot; non-complete graph (i.e. a complete graph with one edge removed) and removing edges, but I&#039;m not sure what to do in the induction step. Any help would be appreciated.

nuvolor8 · Accepted Answer

Step 1Let 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 2This gives us that   χ  (  G  )  ≤  χ  (  G  [      V    1    ]  )  +  χ  (  G  [      V    2    ]  )  −  1 and we are done.