Cohen et al.'s general oriented-cycle subdivision conjecture
Cohen et al.'s general oriented-cycle subdivision conjecture
For positive integers , let 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 , with all replacement paths internally disjoint. The chromatic number of a digraph is denoted by . Cohen et al.'s conjecture. For every positive integers , there exists a constant such that every strongly connected digraph containing no subdivisions of the oriented cycle has chromatic number at most . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.