Heroes in oriented complete multipartite graphs

被引:4
作者
Aboulker, Pierre [1 ]
Aubian, Guillaume [1 ,2 ]
Charbit, Pierre [2 ]
机构
[1] PSL Univ, Ecole Normale Super, DIENS, CNRS, Paris, France
[2] Univ Paris, CNRS, IRIF, Paris, France
关键词
dichromatic number; heroes; multipartite graphs;
D O I
10.1002/jgt.23061
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The dichromatic number of a digraph is the minimum size of a partition of its vertices into acyclic induced subgraphs. Given a class of digraphs C ${\mathscr{C}}$, a digraph H $H$ is a hero in C ${\mathscr{C}}$ if H $H$-free digraphs of C ${\mathscr{C}}$ have bounded dichromatic number. In a seminal paper, Berger et al. give a simple characterisation of all heroes in tournaments. In this paper, we give a simple proof that heroes in quasitransitive oriented graphs (that are digraphs with no induced directed path on three vertices) are the same as heroes in tournaments. We also prove that it is not the case in the class of oriented multipartite graphs, disproving a conjecture of Aboulker, Charbit and Naserasr, and give a characterisation of heroes in oriented complete multipartite graphs up to the status of a single tournament on six vertices.
引用
收藏
页码:652 / 669
页数:18
相关论文
共 15 条
[1]  
Aboulker P., 2022, SIAM J DISCRET MATH, V36
[2]   Decomposing and colouring some locally semicomplete digraphs [J].
Aboulker, Pierre ;
Aubian, Guillaume ;
Charbit, Pierre .
EUROPEAN JOURNAL OF COMBINATORICS, 2022, 106
[3]   Extending the Gyarfas-Sumner conjecture to digraphs [J].
Aboulker, Pierre ;
Charbit, Pierre ;
Naserasr, Reza .
ELECTRONIC JOURNAL OF COMBINATORICS, 2021, 28 (02)
[4]   Chromatic Number of Ordered Graphs with Forbidden Ordered Subgraphs [J].
Axenovich, Maria ;
Rollin, Jonathan ;
Ueckerdt, Torsten .
COMBINATORICA, 2018, 38 (05) :1021-1043
[5]  
Bang-Jensen J, 2018, SPRINGER MONOGR MATH, P1, DOI 10.1007/978-3-319-71840-8_1
[6]   QUASI-TRANSITIVE DIGRAPHS [J].
BANGJENSEN, J ;
HUANG, J .
JOURNAL OF GRAPH THEORY, 1995, 20 (02) :141-161
[7]   Tournaments and colouring [J].
Berger, Eli ;
Choromanski, Krzysztof ;
Chudnovsky, Maria ;
Fox, Jacob ;
Loebl, Martin ;
Scott, Alex ;
Seymour, Paul ;
Thomasse, Stephan .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2013, 103 (01) :1-20
[8]   Induced subgraphs of graphs with large chromatic number. XI. Orientations [J].
Chudnovsky, Maria ;
Scott, Alex ;
Seymour, Paul .
EUROPEAN JOURNAL OF COMBINATORICS, 2019, 76 :53-61
[9]  
Erdos P., 1966, THEORY GRAPHS, P61
[10]  
Gyarfas A., 1975, C MATH SOC J BOLYAI, V10, P801