Bounds on coloring of graph with edges combined from planar and tree graphs.

Question

I am really new to graphs and don't even know how to begin chipping away on following problem.

We have graph $G=(V,E)$ such that $E=E_1\cup E_2$ and $G_1=(V,E_1)$ is planar and $G_2=(V,E_2)$ is a tree. Show that $\chi(G) < 9$.

I've read so far only on basics about graphs and coloring and such abstract problem seems a little beyond me - what simpler ideas should I ponder to make progress on this?

Answer 1

Color $G_1$ properly so that the color of a vertex $v$ is $f(v)\in\{1,2,3,4\}$, you can do this thanks to the four color theorem.

Now color $G_2$ properly so that the color of a vertex $v$ is $g(v)\in\{1,2\}$, you can do this because trees are clearly bipartite.

Now color each vertex $v$ with the ordered pair $(f(v),g(v))$, note there are at most $8$ different options. Clearly no two adjacent vertices $v,u$ can have the same color, because if they share an edge from $G_1$ then $f(u)\neq f(v)$ and if they share an edge from $G_2$ we have $g(u)\neq f(u)$