So this question is seriously flooring me.
Let $G$ be drawn in the plane so that it satisfies:
- The boundary of the infinite region is a cycle $C$
- Every other region has boundary cycle of length $3$
- Every vertex of $G$ not in $C$ has even degree
Show that $\chi(G) \le 3$, where $\chi(G)$ is the chromatic number.
I know I have to use induction and consider two cases for the first step: Whether some two non-consecutive vertices of $C$ are adjacent and in the second case I would delete an edge of $C$ and apply the induction hypothesis.
Can anyone help?
Best Answer
This came up on CS Theory a while back: https://cstheory.stackexchange.com/questions/4027/coloring-planar-graphs
Unfortunately some of the links in that post are dead / not free.
This paper proves a special case of what you mention, that if all vertices are of even degree in a near-triangulation, then the graph is 3-colorable. The key is that such a graph is eulerian, and therefore has an eulerian trail that doesn't cross over itself. Coloring vertices 1, 2, 3, 1, 2, 3, etc. along this trail is a proper 3-coloring.
For the case when $G$ has odd vertices on its boundary, you can construct a planar Eulerian near-triangulation $H$ such that $G \subset H$ and $H$ is Eulerian. Let $C = v_1v_2\ldots v_x$ and suppose $v_j$ and $v_k$ on $C$ are of odd degree. WLOG $k > j$. Add vertices $u_ju_{j+1}\ldots u_{k-1}$ in the exterior region in the obvious order. Then add the edges $v_iu_i$ and $v_{i+1}u_i$ for $j \le i \le k-1$. Now $u_j$ and $u_{k-1}$ are both of odd degree unless $j = k-1$, but we can repeat this process until these two odd vertices are resolved (since the odd vertices continue to get closer). We now have fewer odd vertices, so repeating this process can make all vertices even.