An asymptotically sharp bound on the maximum number of independent transversals

DOI10.37236/11670arXiv2211.06722MaRDI QIDQ6131742FDOQ6131742

Authors:

Publication date: 18 April 2024

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

Abstract: Let $G$ be a multipartite graph with partition $V_1,V_2,ldots,V_k$ of $V(G)$. Let $d_{i,j}$ denote the edge density of the pair $(V_i,V_j)$. An independent transversal is an independent set of $G$ with exactly one vertex in each $V_i$. In this paper, we prove an asymptotically sharp upper bound on the maximum number of independent transversals given the $d_{i,j}$'s.

Full work available at URL: https://arxiv.org/abs/2211.06722

Recommendations

• Independent transversals in \(r\)-partite graphs
• Independent transversals in locally sparse graphs
• Independent Transversals and Independent Coverings in Sparse Partite Graphs
• An average degree condition for independent transversals
• Odd Independent Transversals are Odd

zbMATH Keywords

geometric meanodd cycle decomposition of a graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Enumeration in graph theory (05C30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Cited In (1)

• On density conditions for transversal trees in multipartite graphs

This page was built for publication: An asymptotically sharp bound on the maximum number of independent transversals

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