On the factor-thickness of regular graphs

Abstract

For each r-regular graph G, define a binary sequence θ(G) = (θ1, θ2,..., θr-1) by θk = 0 if G has a k-factor, and θk = 1 otherwise. A binary sequence ε = (εi|i = 1, 2,..., r - 1) is said to be realizable if there exists an r-regular graph G such that θ(G) = ε. In this paper we characterize all binary sequences which are realizable. © 1989 Springer-Verlag.