Premium
Characterization of edge‐colored complete graphs with properly colored Hamilton paths
Author(s) -
Feng Jinfeng,
Giesen HansErik,
Guo Yubao,
Gutin Gregory,
Jensen Tommy,
Rafiey Arash
Publication year - 2006
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.20188
Subject(s) - colored , combinatorics , mathematics , conjecture , graph , edge coloring , discrete mathematics , graph power , line graph , materials science , composite material
An edge‐colored graph H is properly colored if no two adjacent edges of H have the same color. In 1997, J. Bang‐Jensen and G. Gutin conjectured that an edge‐colored complete graph G has a properly colored Hamilton path if and only if G has a spanning subgraph consisting of a properly colored path C 0 and a (possibly empty) collection of properly colored cycles C 1 , C 2 ,…, C d such that $V (C_i) \cap {V(C}_j) =\emptyset$ provided $0 \le i < j \le d$ . We prove this conjecture. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 333–346, 2006