Transversal Structures in Graph Systems: A Survey
摘要
Given a system \(\mathcal {G} =\{G_1,G_2,\dots ,G_m\}\) of graphs/digraphs/hypergraphs on the common vertex set V of size n, an m-edge graph/digraph/hypergraph H with vertices in V is transversal in \(\mathcal {G}\) if there exists a bijection \(\phi :E(H)\rightarrow [m]\) such that \(e \in E(G_{\phi (e)})\) for all \(e\in E(H)\) . In this survey, we consider extremal problems for transversal structures in graph systems. More precisely, we summarize some sufficient conditions that ensure the existence of transversal structures in graph/digraph/hypergraph systems, which generalize several classical theorems in extremal graph theory to transversal versions. We also include a number of conjectures and open problems.