χ‐bounded families of oriented graphs

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

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2018-11, Vol.89 (3), p.304-326
Main Authors: Aboulker, P., Bang‐Jensen, J., Bousquet, N., Charbit, P., Havet, F., Maffray, F., Zamora, J.
Format: Article
Language:English
Subjects:
chromatic number
clique number
Computer Science
Discrete Mathematics
Graph theory
Graphs
χ‐bounded
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.22252