Heroes in oriented complete multipartite graphs

DOI10.1002/JGT.23061arXiv2202.13306MaRDI QIDQ6199386

Author name not available (Why is that?)

Publication date: 23 February 2024

Published in: (Search for Journal in Brave)

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.

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

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

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)