HAL (Le Centre pour la Communication Scientifique Directe) · 2016 · 18 citations · 10 references
Open access
Natural SciencesMathematicsCombinatoricsComputational GeometryGraph VisualizationDirected Acyclic GraphsGraph AlgorithmsGraph ColoringGraph Theory
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$).
10
Paul Erdős · Canadian Journal of Mathematics · 1959 · 602 citations · Full text
Efficient algorithms for graph manipulation
John E. Hopcroft, Robert E. Tarjan · 1971 · 232 citations