Digraphs and variable degeneracy

Abstract

Let $D$ be a digraph, let $p\ge 1$ be an integer, and let $f:V(D)\to {\mathbb{N}}_0^p$ be a vector function with $f=(f_1,f_2,\dots ,f_p)$. We say that $D$ has an $f$-partition if there is a partition $(D_1,D_2,\dots ,D_p)$ into induced subdigraphs of $D$ such that for all $i\in [1,p]$, the digraph $D_i$ is weakly $f_i$-degenerate, that is, in every non-empty subdigraph $D^{\prime }$ of $D_i$ there is a vertex $v$ such that $\min \{d_{D^{\prime }}^{+}(v),d_{D^{\prime }}^{-}(v)\}<f_i(v)$. In this paper, we prove that the condition $f_1(v)+f_2(v)+\dots +f_p(v)\ge \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)$. Moreover, we describe a polynomial time algorithm that (under the previous conditions) either verifies that $(D,f)$ is a bad pair or finds an $f$-partition. 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 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.