Cohen et al.'s general oriented-cycle subdivision conjecture

For positive integers k1,k2,,knk_1,k_2,\ldots,k_n, let C(k1,k2,,kn)C(k_1,k_2,\ldots,k_n) denote the oriented cycle formed by blocks of those lengths. A digraph is strongly connected if every ordered pair of vertices is joined by a directed path, and a subdivision is obtained by replacing each arc with a directed path of length at least 11, with all replacement paths internally disjoint. The chromatic number of a digraph DD is denoted by χ(D)\chi(D). Cohen et al.'s conjecture. For every positive integers k1,k2,,knk_1,k_2,\ldots,k_n, there exists a constant g(k1,k2,,kn)g(k_1,k_2,\ldots,k_n) such that every strongly connected digraph containing no subdivisions of the oriented cycle C(k1,k2,,kn)C(k_1,k_2,\ldots,k_n) has chromatic number at most g(k1,k2,,kn)g(k_1,k_2,\ldots,k_n). This conjecture seeks to extend Bondy's theorem from directed cycles to all oriented cycles; the source does not specify a resolution.

Sources & referencesView supporting material

Primary source

Darine Al-Mniny and Soukaina Zayat, “About subdivisions of four blocks cycles C(k_1,1,k_3,1) in digraphs with large chromatic number”, arXiv:2308.13640 (2023).

Additional references

2 papers in this index state this conjecture (2020–2023). The statement above is taken from the most recent of them; the others are arXiv:2010.10787.

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.