χ-bounded families of oriented graphs
Cargando...
Archivos
Fecha
2018-11
Profesor/a Guía
Facultad/escuela
Idioma
en
Título de la revista
ISSN de la revista
Título del volumen
Editor
Wiley-Liss Inc.
Nombre de Curso
Licencia CC
Licencia CC
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. © 2018 Wiley Periodicals, Inc.
Notas
Indexación Scopus
Palabras clave
Graph, Chromatic Number, Clique, χ-bounded
Citación
Journal of Graph Theory Volume 89, Issue 3, Pages 304 - 326November 2018
DOI
10.1002/jgt.22252