Rainbow and orthogonal paths in factorizations of Kn |
| |
Authors: | András Gyárfás Mehdi Mhalla |
| |
Institution: | 1. Computer and Automation Research Institute, Hungarian Academy of Sciences Budapest, P.O. Box 63, Budapest, Hungary H‐1518;2. Laboratoire LIG‐CNRS, 46 avenue Félix Viallet, 38031 Grenoble, Cedex, France |
| |
Abstract: | For n even, a factorization of a complete graph Kn is a partition of the edges into n?1 perfect matchings, called the factors of the factorization. With respect to a factorization, a path is called rainbow if its edges are from distinct factors. A rainbow Hamiltonian path takes exactly one edge from each factor and is called orthogonal to the factorization. It is known that not all factorizations have orthogonal paths. Assisted by a simple edge‐switching algorithm, here we show that for n?8, the rotational factorization of Kn, GKn has orthogonal paths. We prove that this algorithm finds a rainbow path with at least (2n+1)/3 vertices in any factorization of Kn (in fact, in any proper coloring of Kn). We also give some problems and conjectures about the properties of the algorithm. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 167–176, 2010 |
| |
Keywords: | factorizations of complete graphs rainbow and orthogonal paths |
|
|