Partitions of hypergraphs under variable degeneracy constraints
Partitions of hypergraphs under variable degeneracy constraints
复制标题
可变简并约束下的超图划分
DOI：
10.1002/jgt.22575
复制
发表时间：
2018
影响因子：
0.9
通讯作者：
M. Stiebitz
中科院分区：
文献类型：
--
作者：
Thomas Schweser;M. Stiebitz
本文研究超图到满足退化约束的诱导子超图的划分问题。我们的超图可能有多条边，但没有环。给定一个超图H和一个序列f=(f1，f2，…，Fp)的p≥1个顶点函数fi：v(H)→N0使得f1(V)+f2(V)+⋯+fp(V)≥dh(V)对于所有v∈V(H)，我们想找出一个序列(h1，h2，…，Hp)，使得每个超图Hi都是严格f-退化的，即对每个非空子超图H‘⊆Hi都有一个顶点v∈V(H’)使得dh‘(V)
The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph H and a sequence f=(f1,f2,…,fp) of p≥1 vertex functions fi:V(H)→N0 such that f1(v)+f2(v)+⋯+fp(v)≥dH(v) for all v∈V(H) , we want to find a sequence (H1,H2,…,Hp) of vertex disjoint induced subhypergraphs containing all vertices of H such that each hypergraph Hi is strictly fi ‐degenerate, that is, for every nonempty subhypergraph H′⊆Hi there is a vertex v∈V(H′) such that dH′(v)