TY - JOUR

T1 - Digraphs and variable degeneracy

AU - Bang-Jensen, Jorgen

AU - Schweser, Thomas

AU - Stiebitz, Michael

N1 - 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

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - acyclic digraph

KW - Brooks' theorem

KW - digraph coloring

KW - digraph degeneracy

U2 - 10.1137/20M1386827

DO - 10.1137/20M1386827

M3 - Journal article

AN - SCOPUS:85130593569

SN - 0895-4801

VL - 36

SP - 578

EP - 595

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 1

ER -