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 twovertices $u,v$.Is it possible $G$ to satisfy:All induced $uv$ paths have odd order (even number ofedges).In all proper $k$ colorings, $u$ and $v$ have distinct colors(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 therest vertices of $G$ are new vertices.According to graphclasses coloring odd hole free is NP hardand 3-coloring is unknown.Computer search suggest small gadgets don't exist (modulo errors).
Existence of certain graph gadget related to coloring odd hole free graph
graph theory;graph colouring
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.