Constructing graphs with no independent transversals

DOI10.37236/12429zbMATH Open1543.05188MaRDI QIDQ6574378FDOQ6574378

Authors: Penny Haxell, Ronen Wdowinski 

Publication date: 18 July 2024

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Recommendations

• Degree criteria and stability for independent transversals
• Graphs of low average degree without independent transversals
• Independent transversals in locally sparse graphs
• Algorithms for Weighted Independent Transversals and Strong Colouring
• An average degree condition for independent transversals

zbMATH Keywords

independent transversal\(r\)-partite graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Transversal (matching) theory (05D15)

Cites Work

• Problems and results in extremal combinatorics. I.
• Adapted List Coloring of Graphs and Hypergraphs
• Bounded transversals in multipartite graphs
• Hall's theorem for hypergraphs
• Sets of elements that pairwise generate a linear group
• A tree version of Kőnig's theorem
• Independent systems of representatives in weighted graphs
• The linear arboricity of graphs
• Domination numbers and homology
• A condition for matchability in hypergraphs
• On Forming Committees
• On complete subgraphs of \(r\)-chromatic graphs
• A solution to a colouring problem of P. Erdős
• Santa claus meets hypergraph matchings
• Independent transversals in \(r\)-partite graphs
• Triangulated spheres and colored cliques
• Eigenvalues of \(K_{1,k}\)-free graphs and the connectivity of their independence complexes
• The intersection of a matroid and a simplicial complex
• Complete Subgraphs of r-partite Graphs
• Extremal problems for transversals in graphs with bounded degree
• The clique complex and hypergraph matching
• Bounded size components -- partitions and transversals.
• Independent transversals in locally sparse graphs
• Odd Independent Transversals are Odd
• A note on vertex list colouring
• Single‐conflict colouring
• The circular chromatic index of graphs of high girth
• Title not available (Why is that?)
• The Hamiltonian property of consecutive-\(d\) digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilistic methods in coloring and decomposition problems
• On a list coloring conjecture of Reed
• Asymptotically the list colouring constants are 1
• Finding independent transversals efficiently
• A general framework for hypergraph coloring
• Cooperative colorings and independent systems of representatives
• An average degree condition for independent transversals
• Graphs of low average degree without independent transversals
• Topological connectedness and independent sets in graphs
• Colorings, transversals, and local sparsity
• Degree criteria and stability for independent transversals
• Improved integrality gap in max-min allocation: or topology at the north pole
• A precise condition for independent transversals in bipartite covers

Cited In (4)

• Algorithms for weighted independent transversals and strong colouring
• Algorithms for Weighted Independent Transversals and Strong Colouring
• Degree criteria and stability for independent transversals
• Monochromatic graph decompositions inspired by anti-Ramsey colorings

This page was built for publication: Constructing graphs with no independent transversals

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