0
$\begingroup$

Let $G_1 = (V, E(G_1))$, $G_2= (V, E(G_2))$ be acyclic graphs and $H = (V, E(H))$ be a planar graph on the same group of vertices $V$.

Prove that $G = (V, E(G_1) \cup E(G_2) \cup E(H))$ is 10-colorable.

Got any ideas?

$\endgroup$
0
$\begingroup$

Suppose $G$ is a graph such that any (not necessarily spanning) subgraph of $G$ contains a vertex of degree at most $d$. Then you can $(d+1)$-colour $G$: remove a vertex $v$ of minimum degree, colour the rest (by induction), and then use an available colour on $v$ (which exists, since $v$ has at most $d$ neighbours).

Hence it would suffice to show that for any subset $S \subseteq V$, $G|_S$ has minimum degree at most $9$. The minimum degree is always bounded above by the average degree. Can you use the fact that $G_1$ and $G_2$ are acyclic, and the fact that $H$ is planar, to get what you need?

$\endgroup$
  • $\begingroup$ yeah, I belive i can. $\endgroup$ – Yotam Raz Sep 11 '16 at 17:34

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.