pith. sign in

arxiv: 1605.07762 · v1 · pith:FK3UQA6Cnew · submitted 2016-05-25 · 🧮 math.CO

Subdivisions of oriented cycles in digraphs with large chromatic number

classification 🧮 math.CO
keywords cyclechromaticlargenumberorientedverticesdigraphssubdivision
0
0 comments X
read the original 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$).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.