χ-bounded families of oriented graphs

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

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)304-326
Number of pages23
JournalJournal of Graph Theory
Volume89
Issue number3
DOIs
Publication statusAccepted/In press - 1 Jan 2018

Keywords

  • Chromatic number
  • Clique number
  • χ-bounded

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'χ-bounded families of oriented graphs'. Together they form a unique fingerprint.

Cite this