Independent transversals in locally sparse graphs
From MaRDI portal
Abstract: 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
ot 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.
Recommendations
- Independent Transversals in Sparse Partite Hypergraphs
- Independent Transversals and Independent Coverings in Sparse Partite Graphs
- Lower bounds for independence numbers of some locally sparse graphs
- Independent transversal domination in graphs
- Independent transversals in \(r\)-partite graphs
- Independent transversals of longest paths in locally semicomplete and locally transitive digraphs
- Independence numbers of locally sparse graphs and a Ramsey type problem
- Local transformations of graphs preserving independence number
- Randomly finding independent sets in locally sparse graphs
Cites work
- A note on vertex list colouring
- Asymptotically the list colouring constants are 1
- Complete Subgraphs of r-partite Graphs
- Domination numbers and homology
- Extremal problems for transversals in graphs with bounded degree
- Graph colouring and the probabilistic method
- scientific article; zbMATH DE number 1246230 (Why is no real title available?)
- scientific article; zbMATH DE number 1299964 (Why is no real title available?)
- Independent systems of representatives in weighted graphs
- Independent transversals in \(r\)-partite graphs
- Odd Independent Transversals are Odd
- On a list coloring conjecture of Reed
- On complete subgraphs of r-chromatic graphs
- On the Strong Chromatic Number
- Problems and results in extremal combinatorics. I.
- The linear arboricity of graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The strong chromatic number of a graph
Cited in
(35)- Independent transversals in \(r\)-partite graphs
- Bounded size components -- partitions and transversals.
- Independent coverings and orthogonal colourings
- Cooperative colorings of trees and of bipartite graphs
- Balanced independent sets in graphs omitting large cliques
- Cooperative colorings and independent systems of representatives
- On factors of independent transversals in \(k\)-partite graphs
- An average degree condition for independent transversals
- Cooperative colorings of forests
- Bounded transversals in multipartite graphs
- Independent Transversals and Independent Coverings in Sparse Partite Graphs
- Odd Independent Transversals are Odd
- Independent Transversals in Sparse Partite Hypergraphs
- Finding independent transversals efficiently
- A general framework for hypergraph coloring
- New bounds for the Moser-Tardos distribution
- Hitting all maximum cliques with a stable set using lopsided independent transversals
- Transversal factors and spanning trees
- Independent transversals in bipartite correspondence-covers
- Algorithms for Weighted Independent Transversals and Strong Colouring
- Colorings, transversals, and local sparsity
- Graphs of low average degree without independent transversals
- An asymptotically sharp bound on the maximum number of independent transversals
- Algorithms for weighted independent transversals and strong colouring
- Packing list‐colorings
- Degree criteria and stability for independent transversals
- Cooperative coloring of some graph families
- A precise condition for independent transversals in bipartite covers
- Constructing graphs with no independent transversals
- Polynomial treewidth forces a large grid-like-minor
- Coloring locally sparse graphs
- Bounded degree graphs and hypergraphs with no full rainbow matchings
- Approximate packing of independent transversals in locally sparse graphs
- Hypergraph cooperative coloring
- Extremal problems for transversals in graphs with bounded degree
This page was built for publication: Independent transversals in locally sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2384801)
