跳到主要导航 跳到搜索 跳到主要内容

Counting rainbow triangles in edge-colored graphs

  • Nankai University

科研成果: 期刊稿件文章同行评审

1 引用 (Scopus)

摘要

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).

源语言英语
页(从-至)742-758
页数17
期刊Journal of Graph Theory
107
4
DOI
出版状态已出版 - 12月 2024

学术指纹

探究 'Counting rainbow triangles in edge-colored graphs' 的科研主题。它们共同构成独一无二的学术指纹。

引用此