Counting rainbow triangles in edge-colored graphs (Q6657585)

The paper concerns rainbow triangles in edge-coloured graphs. The minimum colour-degree \(\delta^c(G)\) of an edge-coloured graph \(G\) is the least \(k\) such that every vertex in \(G\) is incident to at least \(k\) different colours. A theorem of \textit{H. Li} [Discrete Math. 313, No. 19, 1893--1896 (2013; Zbl 1277.05065)] says that an \(n\)-vertex edge-coloured graph \(G\) with \(\delta^c(G) \geq (n+1)/2\) contains a rainbow triangle, which is best-possible.\N\NThe authors study the problem of estimating the number of rainbow triangles in similar situations. Their main result says that if \(\delta^c(G) \geq (n+1)/2\), then there are at least \(\delta^c(G)(2 \delta^c(G) - n)n/6\) rainbow triangles in \(G\). This is tight in many cases, as evidenced by rainbowly-coloured balanced complete \(k\)-partite graphs. It also gives the correct order of magnitude for the number of rainbow triangles in the case \(\delta^c(G) = (n+1)/2\). In such a case their formula gives that there are \(\Omega(n^2)\) rainbow triangles, which is shown to be the right order of magnitude as evidenced by two examples provided by the authors.\N\NTheir results follow from the more specific setting of estimating the number of rainbow triangles that contain a given vertex, and they prove many different results and bounds in this vein. Based on this, the authors provide some other variations of their results. For example, they show how to obtain many rainbow triangles all sharing a vertex. Beyond minimum colour-degree conditions, they also obtain a counting version of a result of \textit{H. Broersma} et al. [Australas. J. Comb. 31, 299--311 (2005; Zbl 1061.05030)] which concerns the number of colours adjacent to pairs of vertices.