4
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ Note that your gadget cannot be perfect, since in perfect/Berge graphs, the vertices $u$ and $v$ you describe (they are called an "even pair" in the literature) are such that the graph obtained from $G$ by identifying $u$ and $v$, has the same chromatic number as $G$. $\endgroup$
    – Louis Esperet
    Commented Jul 13, 2015 at 8:03
  • $\begingroup$ @Louis Thank you. I suppose it is more likely to have odd hole rather than odd anti-hole in case it exists? $\endgroup$
    – joro
    Commented Jul 13, 2015 at 8:08
  • $\begingroup$ @Lois This paper claims merging even pairs preserves the chromatic number of any graph: ime.usp.br/~cris/gcomb/pronex/ps-dvi-files/celina/livro.ps.gz $\endgroup$
    – joro
    Commented Jul 13, 2015 at 8:48
  • $\begingroup$ Crossposted on cstheory, attempted answer there: cstheory.stackexchange.com/questions/31982/… $\endgroup$
    – joro
    Commented Jul 14, 2015 at 7:20

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .