<p>One can extract an argument that this cannot work from the paper <a href="http://www.ime.usp.br/~cris/gcomb/pronex/ps-dvi-files/celina/livro.ps.gz" rel="nofollow">found by OP in the MO thread</a>. 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)\}\}$. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-07-13T11:58:40.860Z
Thank you. I allow induced triangles in all cases, does your answer still apply?
joro
CC BY-SA 3.0
2015-07-13T12:13:02.950Z
Check the MO comments about "even pairs" and "merging even pairs preserves the chromatic number", this might disprove it.
joro
CC BY-SA 3.0
2015-07-13T14:16:27.073Z
reverse image - I have updated to get rid of it (and deleted some obsolete comments)
Klaus Draeger
CC BY-SA 3.0
2015-07-14T06:06:08.833Z
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
CC BY-SA 3.0
2015-07-14T06:27:43.420Z
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?
joro
CC BY-SA 3.0
2015-07-14T09:30:36.577Z
The argument merely says that from any given coloring, we can get another where $u,v$ have the same color, contradicting the assumption that their colors always differ. And we don't have to show non-existence of an even path, just existence of an odd (induced) one.
Klaus Draeger
CC BY-SA 3.0
2015-07-14T10:48:19.513Z
Oh, I see now (misunderstood before). This proof is likely correct.
joro
CC BY-SA 3.0
2015-07-15T11:04:41.940Z
Your proof shows: if $u,v$ is even pair, in some proper coloring $u,v$ have the same color, right?
joro
CC BY-SA 3.0
2015-07-15T12:48:49.030Z
Yes, that is it in a nutshell.
Klaus Draeger
CC BY-SA 3.0
2015-07-13T11:46:25.477Z
2015-07-13T14:15:16.173Z
2015-07-13T14:15:16.173Z
Klaus Draeger
<p>Crossposted from <a href="https://mathoverflow.net/questions/211209/existence-of-certain-graph-gadget-related-to-coloring-odd-hole-free-graph">MO</a>.</p>

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

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

<p>Is it possible $G$ to satisfy:</p>

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

<p>If this is possible, there is reduction $F$ to odd hole free $F'$.</p>

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

<p>According to graphclasses coloring odd hole free is NP hard
and 3-coloring is unknown.</p>

<p>Computer search suggest small gadgets don't exist (modulo errors).</p>

<graph-theory><graph-colouring>
Existence of certain graph gadget related to coloring odd hole free graph
joro
# Existence of certain graph gadget related to coloring odd hole free graph

(Asked by: username_0 on 2015-07-13)

Crossposted from [MO](https://mathoverflow.net/questions/211209/existence-of-certain-graph-gadget-related-to-coloring-odd-hole-free-graph).

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

**Tags:** graph-theory, graph-colouring

---

## 1 answers

### Answer by username_1 on 2015-07-13. Score: 4 | Accepted answer

One can extract an argument that this cannot work from the paper [found by OP in the MO thread](http://www.ime.usp.br/~cris/gcomb/pronex/ps-dvi-files/celina/livro.ps.gz). 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.

> **Comments:**
> **username_0**: Thank you. I allow induced triangles in all cases, does your answer still apply?  
> **username_0**: Check the MO comments about "even pairs" and "merging even pairs preserves the chromatic number", this might disprove it.  
> **username_1**: reverse image - I have updated to get rid of it (and deleted some obsolete comments)  
> **username_0**: 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$.  
> **username_0**: 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?  
> **username_1**: The argument merely says that from any given coloring, we can get another where $u,v$ have the same color, contradicting the assumption that their colors always differ. And we don't have to show non-existence of an even path, just existence of an odd (induced) one.  
> **username_0**: Oh, I see now (misunderstood before). This proof is likely correct.  
> **username_0**: Your proof shows: if $u,v$ is even pair, in some proper coloring $u,v$ have the same color, right?  
> **username_1**: Yes, that is it in a nutshell.  

---

