Rainbow triangles sharing one common vertex or edge

Xiaozheng Chen ; Bo Ning

The electronic journal of combinatorics, Tome 32 (2025) no. 3

Résumé

Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the 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 $\delta^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 $\delta^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 $\delta^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 $\delta^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 primary novelty in our proof of the first result lies in the integration of the recent technique for identifying rainbow cycles, which was developed by Czygrinow, Molla, Nagle, and Oursler, with certain counting methods from Li, Ning, Shi, and Zhang [J. Graph Theory, 107(4), 2024]. The proof of the second result is facilitated by the implicit use of the machinery underlying the work on Turán numbers for matchings, as established by Erdős and Gallai.

Détail

DOI : 10.37236/12170

Classification : 05C15, 05C38
Mots-clés : color degree, rainbow triangles