Subdivisions of oriented cycles in digraphs with large chromatic number

被引:14
作者
Cohen, Nathann [1 ]
Havet, Frederic [2 ,3 ]
Lochet, William [2 ,3 ,4 ]
Nisse, Nicolas [2 ,3 ]
机构
[1] Univ Paris Sud, CNRS, LRI, Orsay, France
[2] Univ Nice Sophia Antipolis, CNRS, I3S, Lab Informat Signaux & Syst,UMR 7271, F-06900 Sophia Antipolis, Provence Alpes, France
[3] INRIA Sophia Antipolis Mediterranee, 2004 Route Lucioles, F-06900 Valbonne, France
[4] ENS Lyon, LIP, 46 Allee Italie, F-69364 Lyon, France
关键词
coloring; digraph; subdivision; GRAPHS; LENGTHS;
D O I
10.1002/jgt.22360
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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).
引用
收藏
页码:439 / 456
页数:18
相关论文
共 20 条
[1]   Paths with two blocks in n-chromatic digraphs [J].
Addario-Berry, L. ;
Havet, F. ;
Thomasse, S. .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (04) :620-626
[2]   Oriented trees in digraphs [J].
Addario-Berry, Louigi ;
Havet, Frederic ;
Sales, Claudia Linhares ;
Reed, Bruce ;
Thomasse, Stephan .
DISCRETE MATHEMATICS, 2013, 313 (08) :967-974
[3]  
Bondy A., 2008, GRAPH THEORY
[4]   DICONNECTED ORIENTATIONS AND A CONJECTURE OF LASVERGNAS [J].
BONDY, JA .
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1976, 14 (NOV) :277-282
[5]  
Burr S.A., 1980, C NUMER, V28, P227
[6]   ANTI-DIRECTED SUBTREES OF DIRECTED-GRAPHS [J].
BURR, SA .
CANADIAN MATHEMATICAL BULLETIN-BULLETIN CANADIEN DE MATHEMATIQUES, 1982, 25 (01) :119-120
[7]   ON CHROMATIC NUMBER OF GRAPHS AND SET-SYSTEMS [J].
ERDOS, P ;
HAJNAL, A .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1966, 17 (1-2) :61-&
[8]  
Erds P., 1959, Canadian J. Math., V11, P34
[9]  
Gallai T., 1968, PROC C, P115
[10]   GRAPHS WITH K-ODD CYCLE LENGTHS [J].
GYARFAS, A .
DISCRETE MATHEMATICS, 1992, 103 (01) :41-48