Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza
Open Access
- 12 December 2023
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (1) , 57-66
Abstract
An edge‐coloring of a complete graph with a set of colors is called completely balanced if any vertex is incident to the same number of edges of each color from . Erdős and Tuza asked in 1993 whether for any graph on edges and any completely balanced coloring of any sufficiently large complete graph using colors contains a rainbow copy of . This question was restated by Erdős in his list of “Some of my favourite problems on cycles and colourings.” We answer this question in the negative for most cliques by giving explicit constructions of respective completely balanced colorings. Further, we answer a related question concerning completely balanced colorings of complete graphs with more colors than the number of edges in the graph .Keywords
All Related Versions
This publication has 18 references indexed in Scilit:
- Generalized Sidon setsAdvances in Mathematics, 2010
- Rainbow Turán ProblemsCombinatorics, Probability and Computing, 2006
- Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraintsRandom Structures & Algorithms, 2003
- An Anti-Ramsey TheoremCombinatorica, 2002
- Rainbow Subgraphs in Edge-Colorings of Complete Graphs1993
- Rainbow subgraphs in properly edge‐colored graphsRandom Structures & Algorithms, 1992
- A note on planar difference setsJournal of Combinatorial Theory, Series A, 1985
- On the Geometry of Planar Difference SetsEuropean Journal of Combinatorics, 1984
- Lower bounds for some Ramsey numbersDiscrete Mathematics, 1972
- A theorem in finite projective geometry and some applications to number theoryTransactions of the American Mathematical Society, 1938