Extremal problems for transversals in graphs with bounded degree

DOI10.1007/S00493-006-0019-9MaRDI QIDQ855115zbMATH OpenOpenAlexFDO

Authors 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) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Transversal (matching) theory (05D15)

Recommendations

• Independent transversals in locally sparse graphs
• Graphs of low average degree without independent transversals
• Bounded size components -- partitions and transversals.
• Colorings, transversals, and local sparsity
• An average degree condition for independent transversals

Cited in

(39)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q855115)