Pith. sign in

REVIEW

Subdivisions of oriented cycles in digraphs with large chromatic number

Not yet reviewed by Pith; the record is open.

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1605.07762 v1 pith:FK3UQA6C submitted 2016-05-25 math.CO

Subdivisions of oriented cycles in digraphs with large chromatic number

classification math.CO
keywords cyclechromaticlargenumberorientedverticesdigraphssubdivision
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved
0 comments
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$).

discussion (0)

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