𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Properly coloured Hamiltonian paths in edge-coloured complete graphs

✍ Scribed by J. Bang-Jensen; G. Gutin; A. Yeo

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
251 KB
Volume
82
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider edge-coloured complete graphs. A path or cycle Q is called properly coloured (PC) if any two adjacent edges of Q differ in colour. Our note is inspired by the follou~ng conjecture by B. Bollobis and P. Erdijs (1976): if G is an edge-coloured complete graph on )I vertices in which the maximum monochromatic degree of every vertex is less than [II 2,. then G contains a PC Hamiltonian cycle. We prove that if an edge-coloured complete graph contain\ a PC 2-factor then it has a PC Hamiltonian path. R. Hlggkvist (19%) announced that e~cr! edge-coloured complete graph satisfying Bollobis+Erdiis condition contains a PC Z-factor. Thcsc two results imply that every edge-coloured complete graph satisfying Bollobis-brdiis condition has a PC Hatniltonian path.

πŸ“œ SIMILAR VOLUMES

Edge-coloured complete graphs: Connected
Edge-coloured complete graphs: Connectedness of some subgraphs
✍ Adam Idzik; Jan Komar; Marcin Malawski πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 435 KB

If the edges of a complete graph K,., m/> 4, are painted two colours so that monochromatic K " graphs are connected, then there exists an increasing sequence ( n)n~4 of complete subgraphs whose monochromatic subgraphs are also connected. For more than two colours this is not true, but an analogous f

Characterization of edge-colored complet
Characterization of edge-colored complete graphs with properly colored Hamilton paths
✍ Jinfeng Feng; Hans-Erik Giesen; Yubao Guo; Gregory Gutin; Tommy Jensen; Arash Ra πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 164 KB

## Abstract 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