POLYCHROMATIC HAMILTON CYCLES

被引：39

作者：

FRIEZE, A ^{[1
]}

REED, B ^{[1
]}

机构：

[1] UNIV WATERLOO,DEPT COMBINATOR & OPTIMIZAT,WATERLOO N2L 3G1,ONTARIO,CANADA

来源：

DISCRETE MATHEMATICS | 1993年 / 118卷 / 1-3期

基金：

美国国家科学基金会;

关键词：

D O I：

10.1016/0012-365X(93)90054-W

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The edges of the complete graph K(n) are coloured so that no colour appears more than k = k(n) times, k = [n/(A ln n)], for some sufficiently large A. We show that there is always a Hamiltonian cycle in which each edge is a different colour. The proof technique is probabilistic.

引用

页码：69 / 74

页数：6