Hamiltonian Digraphs Meet Two-Block Cycle Coloring Bound

Two-block cycles sit at a useful point between directed paths and more rigid cycle subdivisions: they consist of two internally vertex-disjoint directed paths with common endpoints, with prescribed minimum lengths $k$ and $\ell$. Addario-Berry, Havet, and Thomassé asked whether excluding all such $C(k,\ell)$ configurations forces a strongly connected digraph to have chromatic number at most $k+\ell-1$ when $k+\ell \geq 4$. This paper settles the Hamiltonian case for the main remaining range: if a Hamiltonian digraph contains no member of $C(k,\ell)$ and $k+\ell \geq 6$, then its chromatic number is at most $k+\ell-1$.

Core Contribution

The contribution is a sharp coloring theorem for Hamiltonian digraphs, not just another sufficient condition for finding a directed cycle pattern. Earlier work of Kim, Kim, Ma, and Park gave $\chi(D) \leq k+\ell$ for $C(k,\ell)$-free Hamiltonian digraphs, and showed that this larger bound can be attained when $k+\ell=5$. Zheng, Lu, Wang, and Chen close the one-color gap for $k+\ell \geq 6$ and state that the resulting $k+\ell-1$ bound is best possible throughout that range.

The paper’s main structural move is to prove a degeneracy statement. Rather than coloring the digraph directly, it studies the underlying graph $G$ of the Hamiltonian digraph $D$. Theorem 1.5, derived near the end of the paper, says that every Hamiltonian digraph with no $C(k,\ell)$ is $(k+\ell-2)$-degenerate. Since every $d$-degenerate graph is $(d+1)$-colorable, this gives the desired $\chi(D) \leq k+\ell-1$ bound.

Technical Approach

The proof is organized around a stronger containment theorem. Theorem 1.6 shows that if the underlying graph of a Hamiltonian digraph has minimum degree at least $k+\ell-1$, then the digraph must contain a member of $C(k,\ell)$. Its contrapositive supplies a low-degree vertex, and a minimal-counterexample deletion argument turns that local degree information into degeneracy.

The visible final proof shows how the authors assemble several case analyses. When $n=k+\ell$, the condition $\delta(G) \geq k+\ell-1$ forces $G$ to be the complete graph $K_{k+\ell}$. Selecting one arc from each unordered pair while preserving the fixed Hamiltonian cycle produces a Hamiltonian tournament contained in $D$. The authors then invoke a tournament result, Theorem 1.1, to find a forbidden two-block cycle, with a special treatment for $(k,\ell)=(4,2)$ using a $D(6,3)$ configuration.

For $n \geq k+\ell+1$, the proof splits by parameter range: $\ell=1$ follows from Theorem 3.1, $\ell=2$ from Theorem 4.1, $\ell \geq 3$ with $k \geq \ell+1$ from Theorem 5.1, and $k=\ell$ from Theorem 5.2. The latter parts of Section 5 are highly local. They track neighbors and non-neighbors along a fixed Hamiltonian cycle, use chords to form two internally disjoint directed paths, and derive contradictions whenever the missing edges fail to follow the narrow pattern forced by the lemmas.

Results and Analysis

The headline result is exact in the Hamiltonian setting: for every positive $k,\ell$ with $k+\ell \geq 6$, every $C(k,\ell)$-free Hamiltonian digraph satisfies $\chi(D) \leq k+\ell-1$, and the paper states that this cannot be improved. Compared with the previous $k+\ell$ upper bound for Hamiltonian digraphs, this removes the remaining additive 1 slack for all sums at least 6. The exception at sum 5 is consistent with prior work, which found examples attaining the older $k+\ell$ bound.

The evidence is mathematical rather than experimental: the paper gives proofs, not measurements. The supported claim is therefore as strong as the proof architecture is sound. The final derivation is clean: Theorem 1.6 supplies a forbidden-cycle contradiction under minimum degree $k+\ell-1$; Theorem 1.5 uses vertex deletion and preservation of Hamiltonicity to prove $(k+\ell-2)$-degeneracy; the coloring bound follows immediately.

Scope and Caveats

The concluding remark is a useful warning about scope. The degeneracy route is specific to Hamiltonian digraphs. For arbitrarily large $N$, the authors describe an orientation of the complete tripartite graph $K_{N,N,1}$ with parts $A,B,\{r\}$, oriented cyclically as $A \to B$, $B \to r$, and $r \to A$. This digraph is strongly connected, has underlying degeneracy $N+1$, and is claimed to be $C(k,\ell)$-free for all positive $k,\ell$ with $k+\ell \geq 6$. So the paper resolves the Hamiltonian version of the Addario-Berry–Havet–Thomassé question, but its degeneracy method cannot extend wholesale to all strongly connected digraphs.