@article{f5e6b93fa7b349908e6b40c2cd8ff168,

title = "χ-bounded families of oriented graphs",

abstract = "A famous conjecture of Gy{\'a}rf{\'a}s and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets P of orientations of P4 (the path on four vertices) similar statements hold. We establish some positive and negative results.",

keywords = "Chromatic number, Clique number, χ-bounded",

author = "P. Aboulker and J. Bang-Jensen and N. Bousquet and P. Charbit and F. Havet and F. Maffray and J. Zamora",

note = "Funding Information: F. Havet, Project Coati, I3S (CNRS, UNSA) and INRIA, Sophia Antipolis, France. Email:

[email protected] Contract grant sponsor: ANR; Contract grant number: ANR-13-BS02-0007; Contract grant sponsor: Labex UCN@Sophia, Sophia Antipo-lis; Contract grant sponsor: Danish Research Council; Contract grant number: 1323-00178B; Contract grant sponsor: Fondecyt Regular; Contract grant number: 1160975; Contract grant sponsor: Nucleo Milenio Informaci{\'o}n y Coordinaci{\'o}n en Redes; Contract grant number: CM/FIC RC130003; Contract grant sponsor: Basal PFB-03 CMM, Universidad de Chile. Funding Information: Part of this work was done while this author was visiting project COATI, Sophia Antipolis. Hospitality and financial support from Labex UCN@Sophia, Sophia Antipolis is gratefully acknowledged. The research of Bang-Jensen was also supported by the Danish Research Council under grant number 1323-00178B. Publisher Copyright: {\textcopyright} 2018 Wiley Periodicals, Inc.",

year = "2018",

month = jan,

day = "1",

doi = "10.1002/jgt.22252",

language = "English",

volume = "89",

pages = "304--326",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "3",

}