TY - JOUR
T1 - Properly colored C4→'s in arc-colored complete and complete bipartite digraphs
AU - Duan, Mengyu
AU - Li, Binlong
AU - Zhang, Shenggui
N1 - Publisher Copyright:
© 2024 Elsevier B.V.
PY - 2025/4
Y1 - 2025/4
N2 - A subdigraph of an arc-colored digraph is called properly colored if its every consecutive arcs have distinct colors. Let D be a digraph. For a digraph H, let pc(D,H) be the minimum number such that every arc-colored digraph DC with c(D)≥pc(D,H) contains a properly colored copy of H, where c(D) is the number of colors of DC. Let Kn↔ and Km,n↔ be the digraphs obtained from the complete graph Kn and the complete bipartite graph Km,n respectively by replacing each edge uv with a pair of symmetric arcs (u,v) and (v,u); and let Ck→ be the directed cycle of length k. In this paper we determine pc(Kn↔,C4→), pc(Km,n↔,C4→) and characterize the corresponding extremal arc-colorings of digraphs.
AB - A subdigraph of an arc-colored digraph is called properly colored if its every consecutive arcs have distinct colors. Let D be a digraph. For a digraph H, let pc(D,H) be the minimum number such that every arc-colored digraph DC with c(D)≥pc(D,H) contains a properly colored copy of H, where c(D) is the number of colors of DC. Let Kn↔ and Km,n↔ be the digraphs obtained from the complete graph Kn and the complete bipartite graph Km,n respectively by replacing each edge uv with a pair of symmetric arcs (u,v) and (v,u); and let Ck→ be the directed cycle of length k. In this paper we determine pc(Kn↔,C4→), pc(Km,n↔,C4→) and characterize the corresponding extremal arc-colorings of digraphs.
KW - Arc-colored digraph
KW - Color number
KW - Properly colored cycle
UR - http://www.scopus.com/inward/record.url?scp=85212092474&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2024.114367
DO - 10.1016/j.disc.2024.114367
M3 - 文章
AN - SCOPUS:85212092474
SN - 0012-365X
VL - 348
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 4
M1 - 114367
ER -