Degree-bounded factorizations of bipartite multigraphs and of pseudographs

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