Digraphs and variable degeneracy

Jorgen Bang-Jensen, Thomas Schweser, Michael Stiebitz

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

39 Downloads (Pure)


Let $D$ be a digraph, let $p \geq 1$ be an integer, and let $f: V(D) \to \mathbb{N}_0^p$ be a vector function with $f=(f_1,f_2,\ldots,f_p)$. We say that $D$ has an $f$-partition if there is a partition $(V_1,V_2,\ldots,V_p)$ of the vertex set of $D$ such that, for all $i \in [1,p]$, the digraph $D_i=D[V_i]$ is weakly $f_i$-degenerate, that is, in every nonempty subdigraph $D'$ of $D_i$ there is a vertex $v$ such that $\min\{d_{D'}^+(v), d_{D'}^-(v)\} < f_i(v)$. In this paper, we prove that the condition $f_1(v) + f_2(v) + \cdots + f_p(v) \geq \max \{d_D^+(v),d_D^-(v)\}$ for all $v \in V(D)$ is almost sufficient for the existence of an $f$-partition and give a full characterization of the bad pairs $(D,f)$. Among other applications, this leads to a generalization of Brooks' theorem as well as the list-version of Brooks' theorem for digraphs, where a coloring of a digraph is a partition of the digraph into acyclic induced subdigraphs. We furthermore obtain a result bounding the $s$-degenerate chromatic number of a digraph in terms of the maximum of maximum in-degree and maximum out-degree.
TidsskriftSIAM Journal on Discrete Mathematics
Udgave nummer1
Sider (fra-til)578-595
StatusUdgivet - 2022

Bibliografisk note

Funding Information:
\ast Received by the editors December 18, 2020; accepted for publication (in revised form) December 3, 2021; published electronically March 3, 2022. https://doi.org/10.1137/20M1386827 \bfF \bfu \bfn \bfd \bfi \bfn \bfg : This work was supported by the Independent Research Fund Denmark under grant DFF 7014-00037B. \dagger IMADA, University of Southern Denmark, DK-5320, Odense M, Denmark ([email protected]). \ddagger Institute of Mathematics, Technische Universit\a"t Ilmenau, D-98684 Ilmenau, Germany (thomas. [email protected], [email protected]).

Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics


Dyk ned i forskningsemnerne om 'Digraphs and variable degeneracy'. Sammen danner de et unikt fingeraftryk.