Cohen–Havet–López–Neumann's oriented-cycle subdivision conjecture

Let CC be an oriented cycle, and let a subdivision of CC be obtained by replacing each arc of CC by a directed path. A digraph is strong if every ordered pair of vertices is joined by a directed path. Cohen–Havet–López–Neumann's conjecture. For every oriented cycle CC, there exists a constant f(C)f(C) such that every strong digraph DD with

χ(D)f(C)\chi(D) \geq f(C)

contains a subdivision of CC. This extends Bondy's theorem from directed cycles to all oriented cycles. It is known for cycles with two blocks and for the antidirected cycle of length 44, but remains open in general.

Sources & referencesView supporting material

Primary source

N. Cohenn, F. Havet, W. Lochet and R. Lopes, “Bispindles in strongly connected digraphs with large chromatic number”, arXiv:1703.02230 (2017).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.