Abstract
Let (Formula presented.) be an edge-colored graph on (Formula presented.) vertices. The minimum color degree of (Formula presented.), denoted by (Formula presented.), is defined as the minimum number of colors assigned to the edges incident to a vertex in (Formula presented.). In 2013, Li proved that an edge-colored graph (Formula presented.) on (Formula presented.) vertices contains a rainbow triangle if (Formula presented.). In this paper, we obtain several estimates on the number of rainbow triangles through one given vertex in (Formula presented.). As a consequence, we prove counting results for rainbow triangles in edge-colored graphs. One main theorem states that the number of rainbow triangles in (Formula presented.) is at least (Formula presented.), which is best possible by considering the rainbow (Formula presented.) -partite Turán graph, where its order is divisible by (Formula presented.). This means that there are (Formula presented.) rainbow triangles in (Formula presented.) if (Formula presented.), and (Formula presented.) rainbow triangles in (Formula presented.) if (Formula presented.) when (Formula presented.). Both results are tight in the 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 (Formula presented.) (i.e., (Formula presented.) rainbow triangles sharing a common vertex).
Original language | English |
---|---|
Pages (from-to) | 742-758 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 107 |
Issue number | 4 |
DOIs | |
State | Published - Dec 2024 |
Keywords
- color degree
- counting subgraphs
- monochromatic degree
- rainbow triangles