We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza.
- Authors
Axenovich, Maria; Clemen, Felix C.
- Abstract
An edge‐coloring of a complete graph with a set of colors C $C$ is called completely balanced if any vertex is incident to the same number of edges of each color from C $C$. Erdős and Tuza asked in 1993 whether for any graph F $F$ on ℓ $\ell $ edges and any completely balanced coloring of any sufficiently large complete graph using ℓ $\ell $ colors contains a rainbow copy of F $F$. 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 F=Kq $F={K}_{q}$ 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 F $F$.
- Subjects
SUBGRAPHS; GRAPH coloring; RAINBOWS; COMPLETE graphs; RAMSEY numbers
- Publication
Journal of Graph Theory, 2024, Vol 106, Issue 1, p57
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.23063