Degree-bounded factorizations of bipartite multigraphs and of pseudographs

AbstractFor 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.We prove 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⌈tr+s−1a⌉+(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.We use 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