χ-bounded families of oriented graphs

P. Aboulker, J. Bang-Jensen, N. Bousquet, P. Charbit, F. Havet, F. Maffray, J. Zamora

Resultado de la investigación: Contribución a una revistaArtículo

2 Citas (Scopus)

Resumen

A famous conjecture of Gyárfá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.

Idioma originalInglés
Páginas (desde-hasta)304-326
Número de páginas23
PublicaciónJournal of Graph Theory
Volumen89
N.º3
DOI
EstadoEn prensa - 1 ene 2018

Áreas temáticas de ASJC Scopus

  • Geometría y topología

Huella Profundice en los temas de investigación de 'χ-bounded families of oriented graphs'. En conjunto forman una huella única.

  • Citar esto

    Aboulker, P., Bang-Jensen, J., Bousquet, N., Charbit, P., Havet, F., Maffray, F., & Zamora, J. (Aceptado/En prensa). χ-bounded families of oriented graphs. Journal of Graph Theory, 89(3), 304-326. https://doi.org/10.1002/jgt.22252