Counting rainbow triangles in edge-colored graphs

Xueliang Li, Bo Ning, Yongtang Shi, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)742-758
Number of pages17
JournalJournal of Graph Theory
Volume107
Issue number4
DOIs
StatePublished - Dec 2024

Keywords

  • color degree
  • counting subgraphs
  • monochromatic degree
  • rainbow triangles

Fingerprint

Dive into the research topics of 'Counting rainbow triangles in edge-colored graphs'. Together they form a unique fingerprint.

Cite this