论文标题
Digraphs和可变变性
Digraphs and variable degeneracy
论文作者
论文摘要
令$ d $为digraph，让$ p \ geq 1 $为整数，让$ f：v（d）\ to \ mathbb {n} _0^p $是$ f =（f_1，f_2，f_2，\ ldots，f_p）$的向量函数。我们说，如果有一个分区$（d_1，d_2，\ ldots，d_p）$，则具有$ f $ d $的分区，以使所有$ i \ in [1，p] $中的所有$ i \ in [1，p] $，d_i $ d_i $ nonnon-dement $ dempraph $ d_i $ demigry是，一个顶点$ v $，使得$ \ min \ {d_ {d'}^+（v），d_ {d'}^ - （v）\} <f_i（v）$。 In this paper, we prove that the condition $f_1(v) + f_2(v) + \ldots + 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)$.此外，我们描述了一种多项式时间算法，该算法（在以前的条件下）要么验证$（d，f）$是一对不好，要么找到$ f $ - 分区。在其他应用中，这导致了Brooks的定理以及Brooks'digraphs定理的列表变化，其中digraph的着色是挖掘物的分配到无循环诱导的次数。此外，我们获得了一个结果，该结果以最大程度和最大值的最大程度的最大程度和最大程度的最大程度来限制了digraph的$ s $分数。
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 $(D_1,D_2,\ldots,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'$ 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) + \ldots + 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)$. 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.
