Classes of digraphs defined by forbidding induced subdigraphs and their chromatic-number

Pierre Aboulker, Universidad Andres Bello, Santiago, Chile
Jeudi 09 juillet 2015 à 11h, salle 26-00/332
Abstract
A class of graphs is $chi$-bounded if there exists a function f such that for any graph G in the class, $chi(G)$ ≤ f (ω(G)). Gyárfas conjectured that for any tree T, the class of graphs that do not contain T as an induced subgraph is $chi$-bounded. We investigate the oriented analogue of this Conjecture. This a joint work with J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, S. Thomassé and J. Zamora
This entry was posted in Events