SEMIREGULAR FACTORIZATIONS OF REGULAR MULTIGRAPHS

An ( r , r +1)‐ factor of a graph G is a spanning subgraph H such that d H ( v )∈{ r , r +1} for all vertices v ∈ V ( G ) . If G is expressed as the union of edge‐disjoint ( r , r +1)‐factors, then this expression is an ( r , r +1)‐ factorization of G . Let μ ( r ) be the smallest integer with the property that if G is a regular loopless multigraph of degree d with d ≥ μ ( r ), then G has an ( r , r +1)‐factorization. It is shown that μ ( r ) ≤ 3 2 r 2 + 3 r + 1 if r is even. The proof employs a novel list‐coloring approach. Together with known results, this shows that μ ( r )= r 2 +1 if r is odd and 3 2 ( r 2 − 2 r ) ≤ μ ( r ) ≤ min { 2 r 2 − 3 r , 3 2 r 2 + 3 r + 1 } if r is even.