Tree versus tree of preorder induced by rainbow forbidden subgraphs
Maezawa · math.CO · 2026-09-05 · 原文
A subgraph H of an edge-colored graph G is rainbow if all the edges of H receive different colors. If G does not contain a rainbow subgraph isomorphic to H, we say that G is rainbow H-free. For connected graphs H_1 and H_2, if there exists an integer t=t(H_1,H_2) such that every rainbow H_1-free edge-colored complete graph colored with t or more colors is rainbow H_2-free, then we write H_1\le H_2. The binary relation \le is reflexive and transitive, and hence it is a preorder. For graphs H_1 and H_2, we write H_1 \equiv H_2 if both H_1 \le H_2 and H_2 \le H_1 hold. Then \equiv is an equivalence relation. If H_1 is a subgraph of H_2, then trivially H_1\le H_2 holds. On the other hand, there exists a pair (H_1, H_2) such that H_1 is a proper supergraph of H_2 and H_1\le H_2 holds. Q.~Cui, Q.~Liu, C.~Magnant and A.~Saito [Discrete Math. {\bf 344} (2021) Article Number 112267] characterized these pairs. %On the other hand, there are few known results regarding the study of \leq for the incomparable with respect to \subseteq. Cui et al. found pairs of graphs H_1 and H_2 such that H_1 \leq H_2 and H_2 \leq H_1, that is,
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
A subgraph H of an edge-colored graph G is rainbow if all the edges of H receive different colors.
If G does not contain a rainbow subgraph isomorphic to H, we say that G is rainbow H-free.
2. 领域脉络
本文类目：math.CO，属于其所在研究脉络的最新进展。
3. 机制拆解
The binary relation \le is reflexive and transitive, and hence it is a preorder.
4. 证据与数字
For connected graphs H_1 and H_2, if there exists an integer t=t(H_1,H_2) such that every rainbow H_1-free edge-colored complete graph colored with t or more colors is rainbow H_2-free, then we write H_1\le H_2.
For graphs H_1 and H_2, we write H_1 \equiv H_2 if both H_1 \le H_2 and H_2 \le H_1 hold.
If H_1 is a subgraph of H_2, then trivially H_1\le H_2 holds.
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
思考本文机制能否迁移到你正在跟进的问题。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。