Premium
Edge‐colored complete graphs without properly colored even cycles: A full characterization
Author(s) -
Li Ruonan,
Broersma Hajo,
Yokota Maho,
Yoshimoto Kiyoshi
Publication year - 2021
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.22684
Subject(s) - colored , combinatorics , mathematics , bipartite graph , chordal graph , enhanced data rates for gsm evolution , discrete mathematics , graph , computer science , artificial intelligence , materials science , composite material
The structure of edge‐colored complete graphs containing no properly colored triangles has been characterized by Gallai back in the 1960s. More recently, Cǎda et al. and Fujita et al. independently determined the structure of edge‐colored complete bipartite graphs containing no properly colored C 4 . We characterize the structure of edge‐colored complete graphs containing no properly colored even cycles, or equivalently, without a properly colored C 4 or C 6 . In particular, we first deal with the simple case of 2‐edge‐colored complete graphs, using a result of Yeo. Next, for k ≥ 3 , we define four classes of k ‐edge‐colored complete graphs without properly colored even cycles and prove that any k ‐edge‐colored complete graph without a properly colored even cycle belongs to one of these four classes.