Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
- 17 October 2003
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 23 (4) , 409-433
Abstract
We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of Kn yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of Kn yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = Kt, we have c1mt2/ln t ≤ f(m, Kt) ≤ c2mt2, and cmt3/ln t ≤ g(m, Kt) ≤ cmt3/ln t, where c1, c2, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003Keywords
This publication has 16 references indexed in Scilit:
- The Probabilistic Method2000
- Properly colored Hamilton cycles in edge-colored complete graphsRandom Structures & Algorithms, 1997
- On uncrowded hypergraphsRandom Structures & Algorithms, 1995
- The strong chromatic number of a graphRandom Structures & Algorithms, 1992
- Ramsey numbers for local coloringsGraphs and Combinatorics, 1987
- An anti-Ramsey theoremGraphs and Combinatorics, 1985
- Extremal uncrowded hypergraphsJournal of Combinatorial Theory, Series A, 1982
- Graphs with Hamiltonian cycles having adjacent lines different colorsJournal of Combinatorial Theory, Series B, 1976
- Alternating Hamiltonian cyclesIsrael Journal of Mathematics, 1976
- A Combinatorial TheoremJournal of the London Mathematical Society, 1950