The minimum degree threshold for perfect graph packings

Details The minimum degree threshold for perfect graph packings The minimum degree threshold for perfect graph packings

2006-03-28

arxiv.org/abs/math/0603665v2

Mathematics

Combinatorics

revised and updated version, accepted for publication in Combinatorica

Scientific paper

Let H be any graph. We determine (up to an additive constant) the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let delta(H,n) denote the smallest integer t such that every graph G whose order n is divisible by |H| and with delta(G) > t contains a perfect H-packing. We show that delta(H,n) = (1-1/\chi*(H))n+O(1). The value of chi*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies k-1 < chi*(H) \le k, where k is the chromatic number of H.

Affiliated with

Also associated with

No associations

Rating

The minimum degree threshold for perfect graph packings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The minimum degree threshold for perfect graph packings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The minimum degree threshold for perfect graph packings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-463631