χ-bounded families of oriented graphs

Vista sencilla de ítem
dc.contributor.authorAboulker P.
dc.contributor.authorBang-Jensen J.
dc.contributor.authorBousquet N.
dc.contributor.authorCharbit P.
dc.contributor.authorHavet F.
dc.contributor.authorMaffray F.
dc.contributor.authorZamora J.
dc.date.accessioned2022-07-02T00:28:43Z
dc.date.available2022-07-02T00:28:43Z
dc.date.issued2018-11
dc.descriptionIndexación Scopuses
dc.description.abstractA 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.es
dc.description.urihttps://onlinelibrary-wiley-com.recursosbiblioteca.unab.cl/doi/10.1002/jgt.22252
dc.identifier.citationJournal of Graph Theory Volume 89, Issue 3, Pages 304 - 326November 2018es
dc.identifier.doi10.1002/jgt.22252
dc.identifier.issn03649024
dc.identifier.urihttps://repositorio.unab.cl/xmlui/handle/ria/23129
dc.language.isoenes
dc.publisherWiley-Liss Inc.es
dc.subjectGraphes
dc.subjectChromatic Numberes
dc.subjectCliquees
dc.subjectχ-boundedes
dc.titleχ-bounded families of oriented graphses
dc.typeArtículoes
Archivos
Bloque original
Mostrando 1 - 1 de 1
Miniatura
Nombre:
Aboulker_P-XBounded_2018.pdf
Tamaño:
249.05 KB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO COMPLETO EN INGLÉS
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FCE - Artículos de Revista