partition of graph in two sets so that the sum of chromatic numbers of the subgraphs is equal to the chromatic number of the original

484 Views Asked by At

How can I prove that exists partition of graph $G$ into two sets $V_1$ and $V_2$ so that for induced subgraphs $G_1$ and $G_2$ applies $x(G)=x(G_1)+x(G_2)$?

My first thought was using a complete subgraph that I know its chromatic number $n$ is the number of its vertices but then is it possible to prove that the rest of the graph has chromatic number $x(G)-n$?

I also thought removing all vertices of a particular color and assuming that's $V_1$ and the rest of the graph is $V_2$ but I don't know if $V_2$ has chromatic number $x(G)-1$ in that case.

1

There are 1 best solutions below

0
On BEST ANSWER

Your second approach sounds promising: let's look more carefully at the chromatic number of $G_2$. Firstly, note the original colouring must still be valid, so $\chi(G_2)\leq\chi(G)-1$. On the other hand, if $G_2$ can be coloured in fewer than $\chi(G)-1$ colours, then you can reattach $G_1$ and obtain a colouring of $G$ in fewer than $\chi(G)$ colours.