Independent transversals in locally sparse graphs

Details Independent transversals in locally sparse graphs Independent transversals in locally sparse graphs

2007-06-14

arxiv.org/abs/0706.2124v1

Mathematics

Combinatorics

16 pages

Scientific paper

Let G be a graph with maximum degree \Delta whose vertex set is partitioned into parts V(G) = V_1 \cup ... \cup V_r. A transversal is a subset of V(G) containing exactly one vertex from each part V_i. If it is also an independent set, then we call it an independent transversal. The local degree of G is the maximum number of neighbors of a vertex v in a part V_i, taken over all choices of V_i and v \not \in V_i. We prove that for every fixed \epsilon > 0, if all part sizes |V_i| >= (1+\epsilon)\Delta and the local degree of G is o(\Delta), then G has an independent transversal for sufficiently large \Delta. This extends several previous results and settles (in a stronger form) a conjecture of Aharoni and Holzman. We then generalize this result to transversals that induce no cliques of size s. (Note that independent transversals correspond to s=2.) In that context, we prove that parts of size |V_i| >= (1+\epsilon)[\Delta/(s-1)] and local degree o(\Delta) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight.

Affiliated with

Also associated with

No associations

Rating

Independent transversals in locally sparse graphs 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 Independent transversals in locally sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Independent transversals in locally sparse graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-331207