Heroes in oriented complete multipartite graphs

DOI10.1002/JGT.23061MaRDI QIDQ6199386zbMATH OpenFDO

Authors Pierre Aboulker, Guillaume Aubian, Pierre Charbit

Publication date 23 February 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2202.13306

zbMATH Keywords

dichromatic numberheroesmultipartite graphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $mathcalC$, a digraph $H$ is a hero in $mcC$ if $H$-free digraphs of $mathcalC$ have bounded dichromatic number. In a seminal paper, Berger at al. give a simple characterization of all heroes in tournaments. In this paper, we give a simple proof that heroes in quasi-transitive oriented graphs 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. We also give a full characterisation of heroes in oriented complete multipartite graphs up to the status of a single tournament on $6$ vertices.

Recommendations

• On heroes in digraphs with forbidden induced forests
• Heroes in orientations of chordal graphs
• Coloring dense digraphs
• Coloring dense digraphs
• Tournaments and colouring

Cites work

• Chromatic number of ordered graphs with forbidden ordered subgraphs
• Coloring dense digraphs
• Decomposing and colouring some locally semicomplete digraphs
• Extension of Gyárfás-Sumner conjecture to digraphs
• scientific article; zbMATH DE number 3747156 (Why is no real title available?)
• scientific article; zbMATH DE number 3480625 (Why is no real title available?)
• Induced subgraphs of graphs with large chromatic number. XI. Orientations
• On coloring digraphs with forbidden induced subgraphs
• Quasi‐transitive digraphs
• The dichromatic number of a digraph
• Tournaments and colouring
• Two results on the digraph chromatic number

Cited in

(3)

• On heroes in digraphs with forbidden induced forests
• \((\overrightarrow{P_6}\), triangle)-free digraphs have bounded dichromatic number
• Generalized competitively orientable complete multipartite graphs

This page was built for publication: Heroes in oriented complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199386)