Counting rainbow triangles in edge-colored graphs

MaRDI QIDQ6386943zbMATH OpenFDO

Authors Xueliang Li, Bo Ning, Yongtang Shi, Shenggui Zhang

Publication date 29 December 2021

Abstract: Let $G$ be an edge-colored graph on $n$ vertices. The minimum color degree of $G$, denoted by $delt{a}^c(G)$, is defined as the minimum number of colors assigned to the edges incident to a vertex in $G$. In 2013, H. Li proved that an edge-colored graph $G$ on $n$ vertices contains a rainbow triangle if $delt{a}^c(G)geqfracn+12$. In this paper, we obtain several estimates on the number of rainbow triangles through one given vertex in $G$. As consequences, we prove counting results for rainbow triangles in edge-colored graphs. One main theorem states that the number of rainbow triangles in $G$ is at least $frac16delt{a}^c(G)(2delt{a}^c(G)-n)n$, which is best possible by considering the rainbow $k$-partite Tur'an graph, where its order is divisible by $k$. This means that there are $Omega(n^2)$ rainbow triangles in $G$ if $delt{a}^c(G)geqfracn+12$, and $Omega(n^3)$ rainbow triangles in $G$ if $delt{a}^c(G)geqcn$ when $c>frac12$. Both results are tight in sense of the order of the magnitude. We also prove a counting version of a previous theorem on rainbow triangles under a color neighborhood union condition due to Broersma et al., and an asymptotically tight color degree condition forcing a colored friendship subgraph $F_k$ (i.e., $k$ rainbow triangles sharing a common vertex).

This page was built for publication: Counting rainbow triangles in edge-colored graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6386943)