Skip to main content
Rainbow Paths
Discrete Mathematics (2010)
  • Domigos Dellamonica Jr., Emory University
  • Colton Magnant, Georgia Southern University
  • Daniel M. Martin, Emory University
A k-rainbow path in a graph with colored edges is a path of length k where each edge has a different color. In this note, we settle the problem of obtaining a constructive k-coloring of the edges of Kn in which one may find, between any pair of vertices, a large number of internally disjoint k-rainbow paths. In fact, our construction obtains the largest possible number of paths. This problem was considered in a less general setting by Chartrand et al.
  • Rainbow paths,
  • Extractors
Publication Date
February 28, 2010
Citation Information
Domigos Dellamonica Jr., Colton Magnant and Daniel M. Martin. "Rainbow Paths" Discrete Mathematics Vol. 310 Iss. 4 (2010) p. 774 - 781 ISSN: 0012-365X
Available at: