## 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 P_{4} (the path on four vertices) similar statements hold. We establish some positive and negative results.

Original language | English |
---|---|

Journal | Journal of Graph Theory |

Volume | 89 |

Issue number | 3 |

Pages (from-to) | 304-326 |

ISSN | 0364-9024 |

DOIs | |

Publication status | Published - Nov 2018 |

## Keywords

- chromatic number
- clique number
- χ-bounded