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 language | English |
|---|---|
| Pages (from-to) | 175-184 |
| Number of pages | 10 |
| Journal | Discrete Applied Mathematics |
| Volume | 370 |
| DOIs | |
| State | Published - 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
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver