pith. sign in

arxiv: 1708.08641 · v1 · pith:O3NRBXSLnew · submitted 2017-08-29 · 🧮 math.CO

Vertex-disjoint properly edge-colored cycles in edge-colored complete graphs

classification 🧮 math.CO
keywords edge-coloredcyclescompletegraphsconjectureproperlydirectedrelationship
0
0 comments X
read the original abstract

It is conjectured that every edge-colored complete graph $G$ on $n$ vertices satisfying $\Delta^{mon}(G)\leq n-3k+1$ contains $k$ vertex-disjoint properly edge-colored cycles. We confirm this conjecture for $k=2$, prove several additional weaker results for general $k$, and we establish structural properties of possible minimum counterexamples to the conjecture. We also reveal a close relationship between properly edge-colored cycles in edge-colored complete graphs and directed cycles in multi-partite tournaments. Using this relationship and our results on edge-colored complete graphs, we obtain several partial solutions to a conjecture on disjoint cycles in directed graphs due to Bermond and Thomassen.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.