Decomposing and colouring some locally semicomplete digraphs

Aboulker Pierre, Aubian Guillaume, Charbit Pierre

Motivated initially by acyclic coloration of digraphs as initiated in arXiv:2009.13319, we prove in this paper various decompositions theorems for certain classes of locally out-semicomplete digraphs, that are digraphs such that the out-neighbourhood of every vertex odes not contain two non adjacent vertices. The main coloring result is that an answer to a question raised in arXiv:2009.13319 : oriented graphs such that the out-neibourhood of every vertex is a transitive tournament have acyclic chromatic number at most $2$.

Knowledge Graph



Sign up or login to leave a comment