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


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 Jul 13 '15 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 Jul 13 '15 at 12:13
  • $\begingroup$ reverse image - I have updated to get rid of it (and deleted some obsolete comments) $\endgroup$ – Klaus Draeger Jul 13 '15 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 Jul 14 '15 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 Jul 14 '15 at 6:27

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.