# Existence of certain graph gadget related to coloring odd hole free graph

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.
• 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$. – joro Jul 14 '15 at 6:06