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$.

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


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.