Rainbow paths |
| |
Authors: | Domingos Dellamonica Jr. Colton Magnant |
| |
Affiliation: | a Emory University, Department of Mathematics and Computer Science, 400 Dowman Dr, Atlanta, GA 30322, USA b Lehigh University, Department of Mathematics, 14 E. Packer Ave., Bethlehem, PA 18015, USA |
| |
Abstract: | 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. (2007) [6]. |
| |
Keywords: | Rainbow paths Extractors |
本文献已被 ScienceDirect 等数据库收录! |
|