Crossposted from MO.

Wondering about the existence of graph gadget related to coloring (or 3-coloring) odd hole free graphs.

Let $G$ be simple $k$-chromatic connected graph with two vertices $u,v$.

Is it possible $G$ to satisfy:

  1. All induced $uv$ paths have odd order (even number of edges).
  2. In all proper $k$ colorings, $u$ and $v$ have distinct colors
  3. (optional) $G$ doesn't contain induced $C_{2n+1}$ for $n>1$

If this is possible, there is reduction $F$ to odd hole free $F'$.

Replace an edge $u'v'$ by the gadget $G$ where $u'=u,v'=v$ and the rest vertices of $G$ are new vertices.

According to graphclasses coloring odd hole free is NP hard and 3-coloring is unknown.

Computer search suggest small gadgets don't exist (modulo errors).


1 Answer 1


One can extract an argument that this cannot work from the paper found by OP in the MO thread. Suppose $G=(V,E)$ is as required, and $c:V\to[k]$ is a $k$-coloring. By the assumption, $c(u)\neq c(v)$. Consider the (bipartite) subgraph $H$ induced by $\{x\in V\ |\ c(x)\in\{c(u),c(v)\}\}$.

If $u$ and $v$ are in the same connected component of $H$, pick any shortest path in $H$ between $u$ and $v$; it is an induced path in $G$, with colors alternating between $c(u),c(v)$, and must have an odd number of edges because the colors at its ends differ. This contradicts the assumption.

So $u,v$ are in different connected components; but then one can toggle the coloring of one of these components to obtain a coloring $c'$ with $c'(u)=c'(v)$, contradiction.

  • $\begingroup$ Thank you. I allow induced triangles in all cases, does your answer still apply? $\endgroup$
    – joro
    Commented Jul 13, 2015 at 11:58
  • $\begingroup$ Check the MO comments about "even pairs" and "merging even pairs preserves the chromatic number", this might disprove it. $\endgroup$
    – joro
    Commented Jul 13, 2015 at 12:13
  • $\begingroup$ reverse image - I have updated to get rid of it (and deleted some obsolete comments) $\endgroup$ Commented Jul 13, 2015 at 14:16
  • $\begingroup$ Are you saying that if $u,v$ is an even pair, in all colorings $c(u)=c(v)$? I believe this follows from preserving the chromatic number when merging $u,v$. $\endgroup$
    – joro
    Commented Jul 14, 2015 at 6:06
  • $\begingroup$ Why non-existence of even path in the bipartite subgraph means no such in the WHOLE graph? A path may pass thru a vertex outside the bipartite graph or am I missing something? $\endgroup$
    – joro
    Commented Jul 14, 2015 at 6:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.