Let $G= (V,E)$ be a graph such that:
$E = E_1 \cup E_2$
$G_1 = (V, E_1)$ is planar
$G_2 = (V, E_2)$ is forest
Proof that chromatic number is $< 9$

My observations

Each planar graph has chromatic number $\le 4$. Also each forest has chromatic number $2$ if $|V| > 1$

But how can I connect that and have convince about chromatic number $<9$?

  • 1
    $\begingroup$ Note that $4\times 2=8<9$. Can you see how to finish? $\endgroup$ – user10354138 May 16 at 16:35

Given colorings $C_1$ of $G_1$ and $C_2$ of $G_2$, construct a new coloring $C_1 \times C_2$ where $C_1 \times C_2(v) = ( C_1(v),C_2(v))$. This is a valid coloring of the graph (check this!). Since there are at most 4 colors in $C_1$ and at most 2 in $C_2$, there are at most 8 in $C_1 \times C_2$.

  • $\begingroup$ Do you mean coloring in use of colors defined by $2$ numbers? $\endgroup$ – trolley May 16 at 17:00
  • $\begingroup$ I don't understand your question. The new coloring is given by ordered pairs of the first coloring and the second coloring. $\endgroup$ – user113102 May 16 at 17:55
  • $\begingroup$ I was asking exactly about that @user113102 $\endgroup$ – trolley May 16 at 17:58

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.