Subdivisions of oriented cycles in digraphs with large chromatic number

Nathann Cohen 1 Frédéric Havet 2 William Lochet 2, 3 Nicolas Nisse 2
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : An {\it 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$ is 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$).
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01277578
Contributor : William Lochet <>
Submitted on : Tuesday, February 23, 2016 - 3:42:13 PM
Last modification on : Monday, November 5, 2018 - 3:36:03 PM
Long-term archiving on : Tuesday, May 24, 2016 - 11:18:00 AM

Files

RR-8865.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01277578, version 1

Citation

Nathann Cohen, Frédéric Havet, William Lochet, Nicolas Nisse. Subdivisions of oriented cycles in digraphs with large chromatic number. [Research Report] RR-8865, LRI - CNRS, University Paris-Sud; LIP - ENS Lyon; INRIA Sophia Antipolis - I3S. 2016, pp.25. ⟨hal-01277578⟩

Share

Metrics

Record views

413

Files downloads

197