# 3-coloring an odd cycle with some constraints

Let $C$ be an odd cycle with vertices $\{v_1,\dots,v_n\}$. Let $U = \{u_1,\dots,u_m\}$ be another disjoint set of vertices and $m \le n$. Each vertex $v_i$ of $C$ is adjacent to exactly $1$ vertex in $U$, and each vertex $u_i$ in $U$ is adjacent to at least $1$ vertex $v_j$ of $C$.

Suppose that $U$ has a fixed $2$-coloring with exactly $2$ colors: $\{1, 2\}$. My guess is that $C$ can be colored with 3 colors $\{1,2,3\}$ so that the coloring of the whole graph is valid. I've done some examples, but I haven't been able to see if or why it's true in general.

This question came up when I was looking at algorithmic reduction of hypergraph 2-colorability to graph 3-colorability.

What I've done in my examples: let the vertices of $C$ be in that order of traversal. For each $v_i$ in order, choose the smallest color available. The next vertex $v_{i+1}$ has at most 2 constraints: from $v_i$ and some $u_j\in U$. So choose the smallest available color for $v_{j+1}$. Continue this way. The problem is the last vertex $v_n$.

• What if $m=1$? Wouldn’t this be a counter example? – Bob Krueger Dec 5 '17 at 1:59
• @BobKrueger You can't color a 1-vertex graph with exactly 2 colors. – Misha Lavrov Dec 5 '17 at 2:05
• @MishaLavrov thank you. I missed that. – Bob Krueger Dec 5 '17 at 2:09

Each vertex around the cycle has exactly one external restriction on its color: "Not $1$" (if it's adjacent to a vertex in $U$ which has color $1$) or "Not $2$" (if it's adjacent to a vertex in $U$ which has color $2$). Moreover, there is at least one vertex of each type, since colors $1$ and $2$ both appear in $U$ and each vertex of $U$ has at least one neighbor on the cycle.

In particular, somewhere on the cycle, a "Not $1$" vertex is adjacent to a "Not $2$" vertex. Orient and label the cycle so that $v_1$ is a "Not $1$" vertex and $v_2$ is a "Not $2$" vertex. Then:

1. Use color $2$ on $v_1$ and color $1$ on $v_2$.
2. Use color $3$ on $v_3, v_5, v_7, \dots, v_n$.
3. Use color $2$ on all remaining "Not $1$" vertices and color $1$ on all remaining "Not $2$" vertices.

All of the "Not $x$" constraints are satisfied. None of the vertices given color $3$ are adjacent. Among the vertices not given color $3$, the only adjacent ones are $v_1$ and $v_2$, which are given different colors.

The idea you reference in your examples reminds me of $d$-degenerate graphs. If you can come up with a vertex ordering $v_i$ where each vertex has back-degree (defined as $|N(v_i) \cap \{v_j : j < i\}|$) at most $d$, then the graph is $d+1$-colorable (proof is the same as greedy coloring). Here you come up with a vertex ordering (of $C$ in the graph with $C$ and $U$) where each vertex has back-degree at most two (i.e., the number of constraints on a vertex at any step of your algorithm is at most two), except possibly the last vertex. The last vertex could have back-degree 3, which would mess up the $2$-degeneracy we were shooting for to get three colors.

The way we fix this is like in Misha's answer: we start with singling out a "Not 1" vertex adjacent to a "Not 2" vertex. Color the "Not 2" vertex 1 initially, and make the vertex ordering go around the cycle starting at the "Not 2" vertex and ending at the "Not 1" vertex from before. While not strictly a $2$-degenerate vertex ordering, this gets rid of the problem we were initially having with the greedy approach.