Degree-bounded factorizations of bipartite multigraphs and of pseudographs

For d ≥ 1 , s ≥ 0 a ( d , d + s ) -graph is a graph whose degrees all lie in the interval { d , d + 1 , … , d + s } . For r ≥ 1 , a ≥ 0 an ( r , r + a ) -factor of a graph G is a spanning ( r , r + a ) -subgraph of G . An ( r , r + a ) -factorization of a graph G is a decomposition of G into edge-disjoint ( r , r + a ) -factors. A graph is ( r , r + a ) -factorable if it has an ( r , r + a ) -factorization. ve a number of results about ( r , r + a ) -factorizations of ( d , d + s ) -bipartite multigraphs and of ( d , d + s ) -pseudographs (multigraphs with loops permitted). For example, for t ≥ 1 let β ( r , s , a , t ) be the least integer such that, if d ≥ β ( r , s , a , t ) then every ( d , d + s ) -bipartite multigraph G is ( r , r + a ) -factorable with x ( r , r + a ) -factors for at least t different values of x . Then we show that β ( r , s , a , t ) = r ⌈ t r + s − 1 a ⌉ + ( t − 1 ) r . Similarly, for t ≥ 1 , let ψ ( r , s , a , t ) be the least integer such that, if d ≥ ψ ( r , s , a , t ) , then each ( d , d + s ) -pseudograph is ( r , r + a ) -factorable with x ( r , r + a ) -factors for at least t different values of x . We show that, if r and a are even, then ψ ( r , s , a , t ) is given by the same formula. this to give tight bounds for ψ ( r , s , a , t ) when r and a are not both even. Finally, we consider the corresponding functions for multigraphs without loops, and for simple graphs.