 |
Journal articles
Subdivisions of oriented cycles in digraphs with large chromatic number
Abstract : An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree 2 and two vertices have in-degree 2).
Cited literature [32 references]
https://hal.archives-ouvertes.fr/hal-01834779
Contributor : Nathann Cohen Connect in order to contact the contributor
Submitted on : Tuesday, July 10, 2018 - 11:06:41 PM
Last modification on : Thursday, January 20, 2022 - 5:29:01 PM
Long-term archiving on: : Thursday, October 11, 2018 - 2:09:18 PM
Contributor : Nathann Cohen Connect in order to contact the contributor
Submitted on : Tuesday, July 10, 2018 - 11:06:41 PM
Last modification on : Thursday, January 20, 2022 - 5:29:01 PM
Long-term archiving on: : Thursday, October 11, 2018 - 2:09:18 PM
File
bounded-chi-cycle.pdf
Files produced by the author(s)