Independent transversals in locally sparse graphs
| dc.creator | Loh, Po-Shen | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-14 | |
| dc.date.accessioned | 2026-07-07T08:10:07Z | |
| dc.date.available | 2026-07-07T08:10:07Z | |
| dc.description | Let G be a graph with maximum degree Δ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 ε> 0, if all part sizes |V_i| >= (1+ε)Δand the local degree of G is o(Δ), then G has an independent transversal for sufficiently large Δ. 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+ε)[Δ/(s-1)] and local degree o(Δ) guarantee the existence of such a transversal, and we provide a construction that shows this is asymptotically tight. | |
| dc.description | 16 pages | |
| dc.identifier | https://arxiv.org/abs/0706.2124 | |
| dc.identifier | http://arxiv.org/abs/0706.2124 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/131744 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C35, 05D15, 05D40 | |
| dc.title | Independent transversals in locally sparse graphs | |
| dc.type | text |