Abstract
Let K c n be an edge-coloured complete graph on n vertices. Let Δmon(Kc n) denote the largest number of edges of the same colour incident with a vertex of Kc n. A properly coloured cycleis a cycle such that no two adjacent edges have the same colour. In 1976, BollobÁs and ErdŐs[6] conjectured that every Kc n with Δmon(Kc n)<⌊n/2⌋contains a properly coloured Hamiltonian cycle. In this paper, we show that for any ε>0, there exists an integer n0 such that every Kc n with Δmon(Kc n)<(1/2–ε)n and n≥n0 contains a properly coloured Hamiltonian cycle. This improves a result of Alon and Gutin [1]. Hence, the conjecture of BollobÁs and ErdŐs is true asymptotically.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon and G. Gutin: Properly colored Hamilton cycles in edge-colored completegraphs, Random Structures Algorithms 11 (1997), 179–186.
N. Alon and J.H. Spencer: The Probabilistic Method, Wiley-Intersci. Ser. DiscreteMath. Optim., John Wiley & Sons, Hoboken, NJ, 2000.
J. Bang-Jensen and G. Gutin: Digraphs, second ed., Springer Monographs in Mathematics, Springer-Verlag London Ltd., London, 2009, Theory, algorithms andapplications.
J. Bang-Jensen, G. Gutin and A. Yeo: Properly coloured Hamiltonian paths inedge-coloured complete graphs, Discrete Appl. Math. 82 (1998), 247–250.
O. Barr: Properly coloured Hamiltonian paths in edge-coloured complete graphswithout monochromatic triangles, Ars Combin. 50 (1998), 316–318.
B. BollobÁs and P. ErdŐs: Alternating Hamiltonian cycles, Israel J. Math. 23(1976), 126–131.
C. C. Chen and D. E. Daykin: Graphs with Hamiltonian cycles having adjacentlines different colors, J. Combin. Theory Ser. B 21 (1976), 135–139.
D. E. Daykin: Graphs with cycles having adjacent lines of different colors, J. Combin.Theory Ser. B 20 (1976), 149–152.
J. Feng, H. Giesen, Y. Guo, G. Gutin, T. Jensen and A. Rafiey: Characteriza-tion of edge-colored complete graphs with properly colored Hamilton paths, J. GraphTheory 53 (2006), 333–346.
S. Fujita and C. Magnant: Properly colored paths and cycles, Discrete Appl. Math. 159 (2011), 1391–1397.
H. Li and G. Wang: Color degree and alternating cycles in edge-colored graphs, Discrete Math. 309 (2009), 4349–4354.
H. Li, G. Wang and S. Zhou: Long alternating cycles in edge-colored completegraphs, Lecture Notes in Computer Science 4613 (2007), 305–309.
A. Lo: A Dirac type condition for properly coloured paths and cycles, Journal ofGraph Theory 76 (2014), 60–87.
A. Lo: An edge-coloured version of Dirac's theorem, SIAM J. Discrete Math. 28(2014), 18–36.
V. Rödl, A. Ruciński and E. SzemerÉdi: An approximate Dirac-type theorem for k-uniform hypergraphs, Combinatorica 28 (2008), 229–260.
J. Shearer: A property of the colored complete graph, Discrete Math. 25 (1979),175–178.
Author information
Authors and Affiliations
Corresponding author
Additional information
The research leading to these results was supported by the European Research Council under the ERC Grant Agreement no. 258345.
Rights and permissions
About this article
Cite this article
Lo, A. Properly coloured Hamiltonian cycles in edge-coloured complete graphs. Combinatorica 36, 471–492 (2016). https://doi.org/10.1007/s00493-015-3067-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00493-015-3067-1