2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning

Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $Î´^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $Î´^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $Î´^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $Î´^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of TurÃ¡n numbers for matching numbers due to ErdÅs and Gallai.

academic

基本信息

论文ID: 2302.00851
标题: Rainbow triangles sharing one common vertex or edge
作者: Xiaozheng Chen (郑州大学), Bo Ning (南开大学)
分类: math.CO (组合数学)
发表时间: 2023年2月2日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2302.00851

摘要

本文研究边着色图中彩虹三角形的存在性问题。对于 $n$ 个顶点的边着色图 $G$ ，顶点 $v$ 的颜色度 $d^c(v)$ 定义为与 $v$ 相邻的边所使用的不同颜色数量。最小颜色度记为 $\delta^c(G)=\min\{d^c(v):v\in V(G)\}$ 。H. Li定理表明，当 $\delta^c(G)\geq \frac{n+1}{2}$ 时，图 $G$ 包含彩虹三角形。受此启发，作者研究了边着色图中的书图(books)和友谊图(friendship graphs)结构。主要结果证明：当 $\delta^c(G)\geq \frac{n+k-1}{2}$ 且 $n\geq 3k-2$ 时， $G$ 包含 $k$ 个共享一条边的彩虹三角形；当 $\delta^c(G)\geq \frac{n+2k-3}{2}$ 且 $n\geq 2k+9$ 时， $G$ 包含 $k$ 个共享一个顶点的彩虹三角形。

研究背景与动机

问题背景

经典三角形问题：Mantel (1907) 证明了 $n$ 个顶点的无三角形图最多有 $\lfloor\frac{n^2}{4}\rfloor$ 条边
结构化三角形：Erdős等人研究了书图 $B_k$ （ $k$ 个共享一条边的三角形）和友谊图 $F_k$ （ $k$ 个共享一个顶点的三角形）的Turán数
彩虹子图：彩虹子图和正确着色子图与许多图论性质密切相关，如经典稳定性结果、Bermond-Thomassen猜想、Caccetta-Häggkvist猜想等

研究动机

H. Li定理的推广：H. Li (2013) 证明了最小颜色度条件 $\delta^c(G)\geq \frac{n+1}{2}$ 保证彩虹三角形的存在
结构化彩虹三角形：自然地考虑多个彩虹三角形共享顶点或边的情况
与经典图论的联系：将经典的书图和友谊图概念推广到边着色图设定

现有方法局限性

现有关于彩虹三角形的研究主要集中在单个三角形的存在性，对于多个彩虹三角形的结构化排列（如共享顶点或边）研究较少。

核心贡献

主要定理3：证明了当 $\delta^c(G)\geq \frac{n+k-1}{2}$ 且 $n\geq 3k-2$ 时，图 $G$ 包含 $k$ 个共享一条边的彩虹三角形（边着色书图 $B_k$ ）
主要定理4：证明了当 $\delta^c(G)\geq \frac{n+2k-3}{2}$ 且 $n\geq 2k+9$ 时，图 $G$ 包含 $k$ 个共享一个顶点的彩虹三角形（边着色友谊图 $F_k$ ）
H. Li定理的改进：当 $k=2$ 时，两个主要结果都改进了H. Li的原始定理
技术创新：结合了Czygrinow等人的彩虹圈技术和最新的计数技术
极值性分析：提供了结果紧性的分析和极值构造

方法详解

任务定义

输入：边着色图 $G=(V,E)$ ，其中 $|V|=n$ ，边着色函数 $C:E\to \{1,2,\ldots,k\}$ 输出：判定 $G$ 是否包含 $k$ 个彩虹三角形共享一条边（或一个顶点） 约束条件：最小颜色度 $\delta^c(G)$ 满足特定阈值

核心概念和技术

1. 颜色度相关定义

颜色度： $d^c(v) = |\{C(uv) : u \in N(v)\}|$
$\alpha$ -邻域： $N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}$
单色度： $d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}$

2. 限制颜色技术

引入Czygrinow等人的"限制颜色"概念：

对于顶点 $v$ 和 $X \subseteq N(v)$ ，如果 $\alpha = C(xy)$ 使得 $vxy$ 构成彩虹 $P_3$ 且 $\alpha \notin C(y, N(y)\setminus X)$ ，则称 $(v,X)$ 对 $y$ 限制颜色 $\alpha$
记 $\sigma_{v,X}(y)$ 为被 $(v,X)$ 限制的颜色数

3. 彩虹三角形计数

$rt(v)$ ：包含顶点 $v$ 的彩虹三角形数量
$rt(v,x)$ ：同时包含顶点 $v$ 和 $x$ 的彩虹三角形数量
$rt(v,X) = \sum_{x \in X} rt(v,x)$

关键引理

引理7（计数引理）

对于边最小图 $G$ 和顶点 $v$ ，有： $rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))$

其中 $N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}$ 。

引理9（单色度分析）

对于具有最大单色度的顶点 $v$ ，有 $B(v) \geq 0$ ，且当 $B(v) = 0$ 时存在特殊结构性质。

证明策略

定理3的证明思路

假设不存在 $k$ 个共享边的彩虹三角形
选择具有最大单色度的顶点 $v$
利用引理7的计数不等式
通过矛盾证明存在满足条件的结构

定理4的证明思路

利用Erdős-Gallai关于匹配数的Turán数理论
构造辅助图 $G^\triangle(v)$ （由包含 $v$ 的彩虹三角形边构成）
分析 $G^\triangle(v)$ 的覆盖数和匹配数
通过精细的度数分析得出矛盾

H. Li定理： $\delta^c(G) \geq \frac{n+1}{2}$ 保证彩虹三角形
Erdős等人结果：关于书图和友谊图的经典Turán数
无色图情况：对应的最小度条件

实验结果

主要结果对比

结构	本文条件	顶点数要求	H. Li条件	改进
$B_2$	$\delta^c \geq \frac{n+1}{2}$	$n \geq 4$	$\delta^c \geq \frac{n+1}{2}$	构造性改进
$F_2$	$\delta^c \geq \frac{n+1}{2}$	$n \geq 13$	$\delta^c \geq \frac{n+1}{2}$	构造性改进
$B_k$	$\delta^c \geq \frac{n+k-1}{2}$	$n \geq 3k-2$	-	新结果
$F_k$	$\delta^c \geq \frac{n+2k-3}{2}$	$n \geq 2k+9$	-	新结果

紧性分析

定理3的紧性：例子1显示当 $n \leq 3k-3$ 时需要更强的颜色度条件 $\delta^c \geq \frac{n+k}{2}$
渐近紧性：当 $k = o(n)$ 时，结果是渐近紧的

结论与讨论

主要结论

成功将H. Li关于彩虹三角形的经典结果推广到多个三角形共享结构的情况
建立了边着色图中书图和友谊图存在性的充分条件
提供了结果的紧性分析和极值构造

局限性

顶点数要求：定理4需要 $n \geq 2k+9$ 的条件相对较强
技术复杂性：证明涉及多个复杂的计数技术和结构分析
一般化程度：结果主要针对特定的共享模式（单边或单顶点）

未来方向

更一般的共享模式：研究更复杂的彩虹三角形排列
其他彩虹结构：推广到彩虹圈、彩虹路径等
算法问题：设计寻找这些结构的高效算法
随机图：在随机边着色图中的对应结果

深度评价

优点

理论贡献显著：成功推广了重要的经典结果，建立了新的理论框架
技术创新：巧妙结合了多种现代技术（限制颜色、计数方法、Turán理论）
结果完整性：不仅给出存在性结果，还分析了紧性和极值情况
写作清晰：论文结构合理，证明思路清楚

不足

证明复杂度高：技术细节较多，可能影响结果的可访问性
应用范围：主要是理论结果，实际应用场景不够明确
常数因子：某些条件中的常数（如 $2k+9$ ）可能不是最优的

影响力

理论价值：为极值组合学和彩虹子图理论提供了新的研究方向
方法论贡献：证明技术可能适用于其他类似问题
后续研究：为相关问题的进一步研究奠定了基础

适用场景

该研究主要适用于：

极值组合学理论研究
图着色理论
结构图论中的存在性问题
组合优化中的子结构检测问题

参考文献

论文引用了29篇重要文献，包括：

H. Li (2013): Rainbow $C_3$ 's and $C_4$ 's in edge-colored graphs
Erdős, Füredi, Gould, Gunderson (1995): Extremal graphs for intersecting triangles
Czygrinow, Molla, Nagle, Oursler (2021): On odd rainbow cycles in edge-colored graphs
等多篇组合数学和图论领域的经典文献