2020/12/17 by Bang-Jensen, Jørgen, Schweser, Thomas, Stiebitz, Michael · 1 citation
#05C20 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2012.09713
Let D be a digraph, let p ≥ 1 be an integer, and let f: V(D) → ℕ0p be a vector function with f=(f1,f2,…,fp). We say that D has an f-partition if there is a partition (D1,D2,…,Dp) into induced subdigraphs of D such that for all i ∈ [1,p], the digraph Di is weakly fi-degenerate, that is, in every non-empty subdigraph D' of Di there is a vertex v such that min\dD'+(v), dD'-(v)\ < fi(v). In this paper, we prove that the condition f1(v) + f2(v) + … + fp(v) ≥ max \dD+(v),dD-(v)\ for all v ∈ 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.