# Proof that chromatic number is $< 9$

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$$?

• Note that $4\times 2=8<9$. Can you see how to finish? – 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$$.
• Do you mean coloring in use of colors defined by $2$ numbers? – trolley May 16 at 17:00