Construct partition such that sum of chromatic numbers is greater than chromatic number of graphShow...
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 such that
I managed to show that we can assume that every vertex x with non-full degree has degree atleast (otherwise, we may take 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.