Factors with Multiple Degree Constraints in Graphs
Richard C. Brewster, Sean R. McGuinness, Morten Hegner Nielsen · SIAM Journal on Discrete Mathematics · 2013
For a graph $G$ and for each vertex $v\in V(G)$, let $\Lambda_G(v) = \{ E_G(v,1), E_G(v,2), \dots , E_G(v,k_v) \}$ be a partition of the edges incident with $v.$ Let $\Lambda_G = \{ \Lambda_G(v) \ | \ v\in V(G) \}.$ We call the pair $(G, \Lambda_G)$ a partitioned graph. Let $k = \max_v k_v$ and let $g,f: V(G) \times \{ 1, \dots ,k \} \rightarrow \mathbb{N}$ and $t,u: V(G) \rightarrow \mathbb{N}$ be functions where, for all vertices $v\in V(G)$, (i) $g(v,i) \le f(v,i) \le d_G(v,i)\ i = 1, \dots ,k_v$, (ii) $u(v) \le t(v) \le d_G(v)$, (iii) $u(v) \le \sum_{i=1}^{k_v}f(v,i)$ and $\sum_{i=1}^{k_v}g(v,i) \le t(v).$ A subgraph $H$ of the partitioned graph is said to be a $(g,f,u,t)$-factor if all vertices $v\in V(G)$ satisfy (a) $g(v,i) \le d_H(v,i) \le f(v,i),\ i = 1, \dots ,k_v$ and (b) $u(v) \le d_H(v) \le t(v)$, where $d_H(v,i)= |E(H) \cap E_G(v,i)|.$ In this paper, we shall show via a reduction to a matching problem, that there is a good algorithm for determining whether a partitioned graph has a $(g,f,u,t)$-factor. Second, we shall also prove a theorem which characterizes the existence of $(0,f,t,u)$-factors in a partitioned graph when $u(v) < f(v,i)$ for all $v$ and $i.$ As a special case, we obtain Lovász's $(g,f)$-factor theorem.