Vertex‐disjoint properly edge‐colored cycles in edge‐colored complete graphs | Zendy

Li Ruonan | Zendy; Broersma Hajo | Zendy; Zhang Shenggui | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

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

Author(s) -

Li Ruonan,

Broersma Hajo,

Zhang Shenggui

Publication year - 2020

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.22536

Subject(s) - combinatorics , mathematics , colored , conjecture , counterexample , vertex (graph theory) , disjoint sets , 1 planar graph , edge coloring , multipartite , enhanced data rates for gsm evolution , discrete mathematics , graph , chordal graph , line graph , computer science , graph power , telecommunications , materials science , physics , quantum mechanics , quantum , quantum entanglement , composite material

It is conjectured that every edge‐colored complete graph G on n vertices satisfyingΔ m o n( G ) ≤ n − 3 k + 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 multipartite 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 content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research