Transversal Structures in Graph Systems: A Survey

Abstract

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$ on $V$ is transversal in $\mathcal{G}$ if there exists a bijection $\ddot{I}•:E(H)\to [m]$ such that $e\in E(G_{\ddot{I}•(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 version. We also include a number of conjectures and open problems.