2024/01/11 by Lucas Picasarri‐Arrieta, Picasarri-Arrieta, Lucas, Clément Rambaud +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2401.05938
Aboulker et al. proved that a digraph with large enough dichromatic number contains any fixed digraph as a subdivision. The dichromatic number of a digraph is the smallest order of a partition of its vertex set into acyclic induced subdigraphs. A digraph is dicritical if the removal of any arc or vertex decreases its dichromatic number. In this paper we give sufficient conditions on a dicritical digraph of large order or large directed girth to contain a given digraph as a subdivision. In particular, we prove that (i) for every integers k,ℓ, large enough dicritical digraphs with dichromatic number k contain an orientation of a cycle with at least ℓ vertices; (ii) there are functions f,g such that for every subdivision F^* of a digraph F, digraphs with directed girth at least f(F^*) and dichromatic number at least g(F) contain a subdivision of F^*, and if F is a tree, then g(F)=|V(F)|; (iii) there is a function f such that for every subdivision F^* of TT3 (the transitive tournament on three vertices), digraphs with directed girth at least f(F^*) and minimum out-degree at least 2 contain F^* as a subdivision.