Complete graphs with no rainbow path
- 20 October 2006
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 54 (3) , 261-266
Abstract
Motivated by questions in Ramsey theory, we consider colorings of the edges of the complete graph Kn that contain no rainbow path Pt+1 of length t. If fewer than t colors are used then certainly there is no rainbow Pt+1. We show that, if at least t colors are used, then very few colorings are possible if t ≤ 5 and these can be described precisely, whereas the situation for t ≥ 6 is qualitatively different. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 261–266, 2007Keywords
This publication has 7 references indexed in Scilit:
- An Upper Bound for Constrained Ramsey NumbersCombinatorics, Probability and Computing, 2006
- Edge colorings of complete graphs without tricolored trianglesJournal of Graph Theory, 2004
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraintsRandom Structures & Algorithms, 2003
- Constrained Ramsey numbers of graphsJournal of Graph Theory, 2002
- Ramsey numbers for local coloringsGraphs and Combinatorics, 1987
- Transitiv orientierbare GraphenActa Mathematica Hungarica, 1967
- A Combinatorial TheoremJournal of the London Mathematical Society, 1950