Semiregular factorization of simple graphs

  • Anthony J. Hilton
  • Jerzy Wojciechowski


A graph G is a (d, d + s)-graph if the degree of each vertex of G lies in the interval [d, d + s]. A (d, d + 1)-graph is said to be semiregular. An (r, r + 1) -factorization of a graph is a decomposition of the graph into edgedisjoint (r, r + 1)-factors.
We discuss here the state of knowledge about (r, r + 1)-factorizations of d -regular graphs and of (d, d + 1)-graphs.
For r, s ≥ 0, let φ(r, s) be the least integer such that, if d ≥ φ(r, s) and G is any simple [d, d + s]-graph, then G has an (r, r + 1)-factorization.
Akiyama and Kano (when r is even) and Cai (when r is odd) showed that φ(r, s) exists for all r, s. We show that, for s ≥ 2, φ(r, s) = r(r + s + 1) + 1. Earlier φ(r, 0) was determined by Egawa and Era, and φ(r, 1) was determined by Hilton.