0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy