χ-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: Article

1 Cita (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 originalEnglish
PublicaciónJournal of Graph Theory
DOI
EstadoAccepted/In press - 1 ene 2018

Huella dactilar

Oriented Graph
Chromatic number
Induced Subgraph
Clique
Digraph
Star
Integer
Tournament
Graph in graph theory
Open Problems
Path
Family

ASJC Scopus subject areas

  • Geometry and Topology

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. https://doi.org/10.1002/jgt.22252
Aboulker, P. ; Bang-Jensen, J. ; Bousquet, N. ; Charbit, P. ; Havet, F. ; Maffray, F. ; Zamora, J. / χ-bounded families of oriented graphs. En: Journal of Graph Theory. 2018.
@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",
year = "2018",
month = "1",
day = "1",
doi = "10.1002/jgt.22252",
language = "English",
journal = "Journal of Graph Theory",
issn = "0364-9024",
publisher = "Wiley-Liss Inc.",

}

Aboulker, P, Bang-Jensen, J, Bousquet, N, Charbit, P, Havet, F, Maffray, F & Zamora, J 2018, 'χ-bounded families of oriented graphs', Journal of Graph Theory. https://doi.org/10.1002/jgt.22252

χ-bounded families of oriented graphs. / Aboulker, P.; Bang-Jensen, J.; Bousquet, N.; Charbit, P.; Havet, F.; Maffray, F.; Zamora, J.

En: Journal of Graph Theory, 01.01.2018.

Resultado de la investigación: Article

TY - JOUR

T1 - χ-bounded families of oriented graphs

AU - Aboulker, P.

AU - Bang-Jensen, J.

AU - Bousquet, N.

AU - Charbit, P.

AU - Havet, F.

AU - Maffray, F.

AU - Zamora, J.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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.

AB - 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.

KW - Chromatic number

KW - Clique number

KW - χ-bounded

UR - http://www.scopus.com/inward/record.url?scp=85045122375&partnerID=8YFLogxK

U2 - 10.1002/jgt.22252

DO - 10.1002/jgt.22252

M3 - Article

AN - SCOPUS:85045122375

JO - Journal of Graph Theory

JF - Journal of Graph Theory

SN - 0364-9024

ER -

Aboulker P, Bang-Jensen J, Bousquet N, Charbit P, Havet F, Maffray F y otros. χ-bounded families of oriented graphs. Journal of Graph Theory. 2018 ene 1. https://doi.org/10.1002/jgt.22252