Rainbow transitive triangles in arc-colored digraphs

Mengyu Duan, Zhiwei Guo, Binlong Li, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

A subdigraph of an arc-colored digraph is rainbow if its all arcs have distinct colors. For two digraphs D and H, let rb(D,H) be the minimum integer such that every arc-colored digraph DC with c(D)≥rb(D,H) contains a rainbow copy of H, where c(D) is the number of colors of DC. Let Kn↔ be the digraph obtained from the complete graph Kn by replacing each edge uv with a pair of symmetric arcs (u,v) and (v,u), and let T3⃗ be the transitive triangle. In this paper we determine rb(Kn↔,T3⃗) and characterize the corresponding extremal arc-colorings of Kn↔. Further, we prove that an arc-colored digraph DC on n vertices contains a rainbow T3⃗ if a(D)+c(D)≥a(Kn↔)+rb(Kn↔,T3⃗). Moreover, if a(D)+c(D)=a(Kn↔)+rb(Kn↔,T3⃗)−1 and DC contains no rainbow T3⃗’s, then D≅Kn↔.

Original languageEnglish
Pages (from-to)175-184
Number of pages10
JournalDiscrete Applied Mathematics
Volume370
DOIs
StatePublished - 31 Jul 2025

Keywords

  • Arc-colored digraph
  • Color number
  • Rainbow digraph
  • Transitive triangle

Fingerprint

Dive into the research topics of 'Rainbow transitive triangles in arc-colored digraphs'. Together they form a unique fingerprint.

Cite this