0
$\begingroup$

I have an idea of how to prove this but I am stuck on how to show part of my argument. I know how to show that $G+H$ is ($m+n$)-colorable, where $\chi(G)=m$ and $\chi(H)=n$, but I am unsure how to show that $G+H$ is not $k$-colorable, for $k<m+n$.

$\endgroup$
3
$\begingroup$

No color in a coloring of $G+H$ can use the same color for a vertex of $G$ and a vertex of $H$, because every vertex of $H$ is connected to every vertex of $G$ in $G+H$. Thus we have to use $\chi(G)+\chi(H)$ colors,$\chi(G)$ to color $G$, and $\chi(H)$ to color H.

$\endgroup$
  • $\begingroup$ That's what I was thinking of. My problem was I wasn't sure how to explain that what you wrote is sufficient to conclude that you need χ(G)+χ(H) colors. Because you could still have vertices of the same color in the part of G+H that came from G. I realize that this must be restricted by the condition on χ(G), but I'm not sure how I can conclude that straight away. Thanks for your answer. $\endgroup$ – A.B Dec 2 '19 at 2:29

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.