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

(46)

• Complexes of directed trees and independence complexes
• Bounded size components -- partitions and transversals.
• Problems and results in extremal combinatorics. I.
• Entropy compression versus Lovász local lemma
• On subgraphs of tripartite graphs
• Distance \(r\)-domination number and \(r\)-independence complexes of graphs
• Cooperative colorings and independent systems of representatives
• Independent transversals in locally sparse graphs
• Independence complexes of claw-free graphs
• On factors of independent transversals in \(k\)-partite graphs
• An average degree condition for independent transversals
• Partitioning of loop-free sperner hypergraphs into transversals
• Bounded transversals in multipartite graphs
• Acyclic systems of representatives and acyclic colorings of digraphs
• Fair representation by independent sets
• Transversals of Vertex Partitions in Graphs
• Two disjoint independent bases in matroid-graph pairs
• Finding independent transversals efficiently
• Topology of clique complexes of line graphs
• On the homology of independence complexes
• New bounds for the Moser-Tardos distribution
• An Extremal Graph Problem with a Transcendental Solution
• A Density Turán Theorem
• Coloring Graphs with Dense Neighborhoods
• Bounding the projective dimension of a squarefree monomial ideal via domination in clutters
• Transversal factors and spanning trees
• Complete subgraphs in a multipartite graph
• 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
• A precise condition for independent transversals in bipartite covers
• Constructing graphs with no independent transversals
• Polynomial treewidth forces a large grid-like-minor
• On density conditions for transversal trees in multipartite graphs
• Bounded degree graphs and hypergraphs with no full rainbow matchings
• A stability theorem for multi-partite graphs
• On size multipartite Ramsey numbers involving complete graphs
• Approximate packing of independent transversals in locally sparse graphs
• A precise condition for independent transversals in bipartite covers (extended abstract)
• Extremal hypergraphs for Ryser's conjecture
• Stanley-Reisner ideals of higher independence complexes of chordal graphs
• Subgraph transversal of graphs
• On \(r\)-dynamic chromatic number of 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)