Rainbow triangles sharing one common vertex or edge

Abstract

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 $\hat{I}{´}^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 $\hat{I}{´}^c(G)\ge \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\ge 2$ be a positive integer. We prove that if $\hat{I}{´}^c(G)\ge \frac{n+k-1}{2}$ where $n\ge 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $\hat{I}{´}^c(G)\ge \frac{n+2k-3}{2}$ where $n\ge 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.

17 pages