Rainbow spanning structures in graph and hypergraph systems

DOI10.1017/FMS.2023.92MaRDI QIDQ6052079zbMATH OpenOpenAlexFDO

Authors

Publication date 23 October 2023

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

rainbow clique-factorssubgraph containment problems

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

Abstract: We study the following rainbow version of subgraph containment problems in a family of (hyper)graphs, which generalizes the classical subgraph containment problems in a single host graph. For a collection $extbfG=G_1,G_2,ldots,G_m$ of not necessarily distinct $k$-graphs on the same vertex set $[n]$, a (sub)graph $H$ on $[n]$ is rainbow if there exists an injection $varphi:E(H)ightarrow[m]$ such that $einE(G_{varphi(e)})$ for each $einE(H)$. Note that if $|E(H)|=m$, then $varphi$ is a bijection and thus $H$ contains exactly one edge from each $G_i$. Our main results focus on rainbow clique-factors in (hyper)graph systems with minimum $d$-degree conditions. Specifically, we establish the following: (1) A rainbow analogue of an asymptotical version of the Hajnal--Szemer'{e}di theorem, namely, if $tmidn$ and $delta(G_i)geq(1-frac1t+varepsilon)n$ for each $$, then $extbfG$ contains a rainbow $K_t$-factor; (2) Essentially a minimum $d$-degree condition forcing a perfect matching in a $k$-graph also forces rainbow perfect matchings in $k$-graph systems for $din[k-1]$. The degree assumptions in both results are asymptotically best possible (although the minimum $d$-degree condition forcing a perfect matching in a $k$-graph is in general unknown). For (1) we also discuss two directed versions and a multipartite version. Finally, to establish these results, we in fact provide a general framework to attack this type of problems, which reduces it to subproblems with finitely many colors.

Recommendations

• Rainbow factors in hypergraphs
• Rainbow \(H\)-factors
• Rainbow spanning subgraphs in bounded edge-colourings of graphs with large minimum degree
• Rainbow Hamilton cycles in random graphs and hypergraphs
• Existences of rainbow matchings and rainbow matching covers

Cites work

• A better bound on the size of rainbow matchings
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• A multipartite Hajnal-Szemerédi theorem
• A Multipartite Version of the Hajnal–Szemerédi Theorem for Graphs and Hypergraphs
• A rainbow \(r\)-partite version of the Erdős-Ko-Rado theorem
• A rainbow version of Mantel's theorem
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Almost \(H\)-factors in dense graphs
• An approximate version of a conjecture of Aharoni and Berger
• An extension of the Hajnal-Szemerédi theorem to directed graphs
• Asymptotic behavior of the chromatic index for hypergraphs
• Critical chromatic number and the complexity of perfect packings in graphs
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Matchings in 3-uniform hypergraphs
• Near perfect coverings in graphs and hypergraphs
• On a rainbow version of Dirac's theorem
• On directed versions of the Corrádi-Hajnal corollary
• On directed versions of the Hajnal-Szemerédi theorem
• On Rainbow Matchings for Hypergraphs
• On the maximal number of independent circuits in a graph
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Proof of the Alon-Yuster conjecture
• Rainbow factors in hypergraphs
• Rainbow matchings for 3-uniform hypergraphs
• Rainbow matchings in bipartite multigraphs
• Rainbow matchings in properly-colored hypergraphs
• Rainbow Odd Cycles
• Rainbow pancyclicity in graph systems
• Rainbow perfect matchings for 4-uniform hypergraphs
• Rainbow Turán Problems
• Some Theorems on Abstract Graphs
• The Erdős matching conjecture and concentration inequalities
• The minimum degree threshold for perfect graph packings
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The size of a hypergraph and its matching number
• Transversal factors and spanning trees
• Transversals in row-latin rectangles
• Variants of the Hajnal-Szemer�di Theorem

Cited in

(13)

• Concentration of rainbow \(k\)-connectivity of a multiplex random graph
• Decompositions into spanning rainbow structures
• Rainbow Pancyclicity in a Collection of Graphs Under the Dirac-type Condition
• Vertex-bipancyclicity in a bipartite graph collection
• Transversal Hamilton cycle in hypergraph systems
• Transversals in a collection of stars or generic trees
• Stability of transversal Hamilton cycles and paths
• Transversal panconnectedness in graph collections
• Rainbow directed version of Dirac's theorem
• Universality for transversal Hamilton cycles
• Erratum to: ``Rainbow spanning structures in graph and hypergraph systems
• Transversal Hamilton paths and cycles
• Transversal Hamilton cycle in the hypergraph system

This page was built for publication: Rainbow spanning structures in graph and hypergraph systems

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