TY - JOUR
T1 - Rainbow transitive triangles in arc-colored digraphs
AU - Duan, Mengyu
AU - Guo, Zhiwei
AU - Li, Binlong
AU - Zhang, Shenggui
N1 - Publisher Copyright:
© 2025
PY - 2025/7/31
Y1 - 2025/7/31
N2 - 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↔.
AB - 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↔.
KW - Arc-colored digraph
KW - Color number
KW - Rainbow digraph
KW - Transitive triangle
UR - http://www.scopus.com/inward/record.url?scp=105002025894&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2025.04.011
DO - 10.1016/j.dam.2025.04.011
M3 - 文章
AN - SCOPUS:105002025894
SN - 0166-218X
VL - 370
SP - 175
EP - 184
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -