5
$\begingroup$

So this question is seriously flooring me.

Let $G$ be drawn in the plane so that it satisfies:

  1. The boundary of the infinite region is a cycle $C$
  2. Every other region has boundary cycle of length $3$
  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?

2 Answers 2

3

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.

  • 0
    Let us know if you find a correct proof by induction. I think this might be harder to prove than it seems though, and so an inductive proof would have to be very diligently crafted.2012-11-25
1

We induct on $|E(G)|$. The base case is trivial.

Suppose first that there are two non-consecutive vertices $u, v$ of $C$ which are adjacent. Let $e$ be the edge joining them. Then, $e$ partitions the graph into two graphs $G_1$ and $G_2$ on either side of $e$ in the plane, both of which satisfy the induction hypothesis, so $\chi(G_1), \chi(G_2) \leq 3$. Permuting the colors of (say) $G_2$ appropriately so that $u$ and $v$ are colored identically in $G_1$ and $G_2$, we obtain a 3-coloring of $G$, so $\chi(G) \leq 3$.

Otherwise, no two nonconsecutive vertices of $C$ are adjacent. Let $w_0, w_1$ be any consecutive vertices on $C$. We know that there is a vertex $u \in V(G) - V(C)$ with $w_0 u, w_1 u \in E(G)$. By the induction hypothesis, the graph $G' = G \setminus w_0 w_1$ has $\chi(G') \leq 3$. I claim that any 3-coloring of $G'$ has $w_0$ and $w_1$ as different colors, so that this coloring extends to a 3-coloring of $G$.

Suppose not, i.e. $w_0$ and $w_1$ are colored identically, and $u$ is colored differently. Consider the triangles incident to $u$, with vertices $u w_i w_{i + 1}$. Since $u$ has even degree, then the path $P = w_1 w_2 \ldots w_{\deg(u) - 1} w_0$ has odd length. Our 3-coloring of $G'$ determines that $P$ is 2-colored, and a 2-colored odd path has opposite colored ends (easily verified), which is a contradiction.