An edge-colored version of Dirac's theorem

Allan Lo*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


Let G be an edge-colored graph. The minimum color degree δc(G) of G is the largest integer k such that for every vertex ν, there are at least k distinct colors on edges incident to ν. We say that G is properly colored if no two adjacent edges have the same color. In this paper, we show that every edge-colored graph G with δc(G) ≥ 2|G|/3 contains a properly colored 2-factor. Furthermore, we show that for any ε > 0 there exists an integer n0 such that every edge-colored graph G with |G| = n ≥ n0 and δc(G) ≥ (2/3 + ε)n contains a properly colored cycle of length ℓ for every 3 ≤ ℓ ≤ n. This result is best possible in the sense that the statement is false for δc(G) < 2n/3.

Original languageEnglish
Pages (from-to)18-36
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Issue number1
Publication statusPublished - 2 Jan 2014


  • 2-factor
  • Hamiltonian cycle
  • Proper edge-coloring

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'An edge-colored version of Dirac's theorem'. Together they form a unique fingerprint.

Cite this