Substructures in digraphs

NEW

Problem: Reconstructed conjecture: For every integer $k\ge 1$, there is an integer $f(k)$ such that every finite strong digraph $D$ with ordinary chromatic number $\chi(D)>f(k)$ contains a subdigraph $H$ with $\chi(H)\ge k$ and with a directed Hamiltonian cycle. Here $\chi(D)$ means the chromatic number of the underlying undirected graph. The statement is exactly the conjecture text; the counterexample below works even for oriented graphs and for induced/non-induced interpretations of “subdigraph.”

Result: The conjecture is false. In fact, for every $M$ there is a finite strong oriented graph $D$ with $\chi(D)>M$, but every subdigraph of $D$ having a Hamiltonian cycle has chromatic number at most $4$. Hence no $f(5)$ can exist.

Let $S_n$ be the shift graph: its vertices are pairs $(i,j)$ with $1\le i<j\le n$, and $(i,j)$ is adjacent to $(j,\ell)$ whenever $i<j<\ell$. Orient every such edge as

Call this acyclic oriented graph $A_n$.

The chromatic numbers $\chi(S_n)$ are unbounded. Indeed, if $S_n$ has a $q$-coloring $c$, define

For $i<j$, the color $c(i,j)$ lies in $C_i$ but not in $C_j$, since otherwise some $(j,\ell)$ would have the same color while adjacent to $(i,j)$. Thus the $C_i$ are $n$ distinct subsets of a $q$-element set, so $n\le 2^q$. Hence $\chi(S_n)\ge \log_2 n$.

Now build $D_n$ from $A_n$ by adding two vertices $a,b$, arcs

for every $v\in V(A_n)$, and no other arcs. This is a strong oriented graph: from any shift vertex $u$ to any shift vertex $v$, there is a path

Also $a,b$ reach and are reached by all vertices.

The underlying graph of $D_n$ is the join of $S_n$ with a $K_2$, so

which is unbounded.

It remains to bound the chromatic number of Hamiltonian subdigraphs. The digraph $A_n$ is acyclic, since every arc $(i,j)\to(j,\ell)$ strictly increases the second coordinate. Therefore every directed cycle in $D_n$ has the form

where $v_1,\dots,v_t$ is a directed path in $A_n$.

Such a directed path has vertices

with $x_0<x_1<\cdots<x_t$. In the shift graph, nonconsecutive vertices of this list are not adjacent; hence these vertices induce an ordinary path, so they are bipartite.

Thus the vertex set of any directed cycle in $D_n$ induces a graph consisting of a bipartite graph plus the adjacent universal vertices $a,b$. Its chromatic number is at most $4$.

If $H\subseteq D_n$ has a Hamiltonian cycle $C$, then $V(H)=V(C)$, and $H\subseteq D_n[V(C)]$. Hence

So $D_n$ contains no Hamiltonian subdigraph of chromatic number at least $5$, while $\chi(D_n)$ is arbitrarily large. This disproves the conjecture.

Citation: No external resolution is used; the counterexample above is complete. The shift-graph chromatic lower bound is proved in the argument.