Multicolored Hamilton Cycles and Perfect Matchings in Pseudorandom Graphs

Research output: Contribution to journalArticle

10 Citations (Scopus)


Given 0 <p <1, we prove that a pseudorandom graph G with edge density p and sufficiently large order has the following property: Consider any red/blue-coloring of the edges of G and let r denote the proportion of edges which have the color red. Then there is a Hamilton cycle C so that the proportion of red edges of C is close to r. The analogue also holds for perfect matchings instead of Hamilton cycles. We also prove a bipartite version which is used elsewhere to give a minimum-degree condition for the existence of a Hamilton cycle in a 3-uniform hypergraph.
Original languageEnglish
Pages (from-to)273-286
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - 1 Jan 2006


  • perfect matchings
  • Hamilton cycles
  • pseudorandom graphs
  • random graphs


Dive into the research topics of 'Multicolored Hamilton Cycles and Perfect Matchings in Pseudorandom Graphs'. Together they form a unique fingerprint.

Cite this