Chromatic number in a union of planar graphs

Question

I am trying to solve the following problem:

Let $G_1, G_2, \dots,G_{100}$ be $100$ planar graphs on the same vertex set $V$ , with edge sets $E_1, E_2,...,E_{100}$, respectively, and consider the graph $G = (V, \bigcup_{i=1}^{100}E_i)$ which is the union of the graphs $G_1, G_2,\dots,G_{100}$. Prove that $\chi(G) ≤ 600$.

I tried to play around with the inequality $E(G) \leq 3 |G| - 6$ that holds for any planar graph, and also with the fact that we can colour any planar graph with 4 colours but I didn't manage to advance after that. I also though of induction on the number of vertices so that I could do that for an arbitrary set of vertices but this didn't help me either.

Can anyone provide a hint/direction so I can make some progress?

Answer 1

I think I have the answer. the $G_1, ..., G_{100}$ are planar graphs on the same set of vertices, thus |V| is the same for all $G_i$.

We know $|E(G_i)|≤3|V|−$6 $\forall i $, since they are all planar thus $ |\bigcup_{i=1}^{100}E_i| \leq |\sum_{i=1}^{100} E_i| ≤100 (3|V|-6)= 300|V|-600$

For convenience let $ E = \bigcup_{i=1}^{100}E_i$

By the degree sum formula or handshake lemma,$\sum_{v} deg(v) = 2|E| \leq 2*(300|V|-600) = 600 |V|-1200 $, thus there exists (proof by contradiction or average degree) a vertex $v$ with degree strictly less than 600, i.e. degree less than or equal to 599. Thus since every subgraph of the union of 100 planar graphs has a vertex of degree less than or equal to 599, the graph is by definition 599- degenerate and therefore 600-colourable.

Is this correct?

Answer 2

The inequality $|E(G)| \le 3 |V(G)| - 6$ is a more useful direction to go in here than the $4$-color theorem. The proof of this result is more similar to the proof of the $6$-color theorem which, in summary, goes as follows:

• From the inequality above, it follows that the average degree of any planar graph is strictly less than $6$, so there must be a vertex of $v$ degree less than $6$: at most $5$.
• We proceed by induction on the number of vertices. By the inductive hypothesis, we can color $G-v$ with $6$ colors.
• We can extend the coloring of $G-v$ to a coloring of $G$ by coloring $v$ a color different from the colors used on its neighbors (there are at most $5$ neighbors, and $6$ colors, so one color is left unused).

This argument generalizes to an argument based on the degeneracy of a graph. A $k$-degenerate subgraph is one in which every subgraph has a vertex of degree at most $k$. The inequality above shows that any planar graph is $5$-degenerate, and a similar inductive argument shows that all $k$-degenerate graphs are $(k+1)$-colorable.

So if you prove that the union of $100$ planar graphs is $599$-degenerate, you'll have a proof that it's $600$-colorable.