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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Transversal Structures in Graph Systems: A Survey

  • Wanting Sun,
  • Guanghui Wang,
  • Lan Wei

摘要

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.