Extremal problems for transversals in graphs with bounded degree

DOI10.1007/s00493-006-0019-9zbMath1106.05100OpenAlexW2067487847MaRDI QIDQ855115

Tibor Szabó, Gábor Tardos

Publication date: 2 January 2007

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.11850/24692

zbMATH Keywords

extremal problemsgraphs with bounded degreeindependent transversals

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Transversal (matching) theory (05D15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (31)

Distance \(r\)-domination number and \(r\)-independence complexes of graphs ⋮ Complete subgraphs in a multipartite graph ⋮ Topology of clique complexes of line graphs ⋮ Bounded transversals in multipartite graphs ⋮ On the homology of independence complexes ⋮ Independent transversals in locally sparse graphs ⋮ On factors of independent transversals in \(k\)-partite graphs ⋮ An average degree condition for independent transversals ⋮ Colorings, transversals, and local sparsity ⋮ Deterministic algorithms for the Lovász local lemma: Simpler, more general, and more parallel ⋮ Graphs of low average degree without independent transversals ⋮ Chordal graphs, higher independence and vertex decomposable complexes ⋮ On an \(f\)-coloring generalization of linear arboricity of multigraphs ⋮ Packing list‐colorings ⋮ Fair Representation by Independent Sets ⋮ On \(r\)-dynamic chromatic number of graphs ⋮ New bounds for the Moser‐Tardos distribution ⋮ Problems and results in extremal combinatorics. I. ⋮ Polynomial treewidth forces a large grid-like-minor ⋮ Independence complexes of claw-free graphs ⋮ Two disjoint independent bases in matroid-graph pairs ⋮ Entropy compression versus Lovász local lemma ⋮ Extremal hypergraphs for Ryser's conjecture ⋮ Acyclic systems of representatives and acyclic colorings of digraphs ⋮ Complexes of directed trees and independence complexes ⋮ Finding independent transversals efficiently ⋮ Coloring Graphs with Dense Neighborhoods ⋮ Bounding the projective dimension of a squarefree monomial ideal via domination in clutters ⋮ On subgraphs of tripartite graphs ⋮ Cooperative colorings and independent systems of representatives ⋮ A Density Turán Theorem

This page was built for publication: Extremal problems for transversals in graphs with bounded degree