BINDING NUMBERS OF GRAPHS AND THE EXISTENCE OF <i>k</i>-FACTORS

Abstract

We prove that, if k ≥ 2 is an integer and G is a graph with p ≥ 4k − 6 vertices and binding number b(G) such that kp is even and b(G) > (2k − 1)(p − 1)/[k(p − 2) − 3], then G has a k-factor. This lower bound on b(G) is best possible for all values of p and k such that (p +4)/ (4k−2) is an integer. Also, if p>k≥2 and kp is even and b(G)≥ (p − 1)/2(√kp − k), then again G has a k-factor, and this bound on b(G) is roughly best possible if p < 4k.