Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza

DOI10.1002/JGT.23063MaRDI QIDQ6201025zbMATH OpenOpenAlexFDO

Authors Maria Axenovich, Felix Christian Clemen

Publication date 25 March 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2209.13867

zbMATH Keywords

edge-coloringsrainbow subgraphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: An edge-coloring of a complete graph with a set of colors $C$ is called completely balanced if any vertex is incident to the same number of edges of each color from $C$. ErdH{o}s and Tuza asked in $1993$ whether for any graph $F$ on $ell$ edges and any completely balanced coloring of any sufficiently large complete graph using $ell$ colors contains a rainbow copy of $F$. This question was restated by ErdH{o}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=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$.

Recommendations

• Balanced edge-colorings avoiding rainbow cliques of size four
• scientific article; zbMATH DE number 434896
• More on rainbow cliques in edge-colored graphs
• A rainbow Erdös-Rothschild problem
• Colored unavoidable patterns and balanceable graphs

Cites work

• A note on planar difference sets
• Additive Combinatorics
• An anti-Ramsey theorem
• An asymptotic version of the prime power conjecture for perfect difference sets
• Generalized Sidon sets
• scientific article; zbMATH DE number 434896 (Why is no real title available?)
• scientific article; zbMATH DE number 2154271 (Why is no real title available?)
• scientific article; zbMATH DE number 889951 (Why is no real title available?)
• scientific article; zbMATH DE number 3069342 (Why is no real title available?)
• Local Anti-Ramsey Numbers of Graphs
• Lower bounds for some Ramsey numbers
• On restricted colourings of \(K_ n\)
• On the geometry of planar difference sets
• Problems on cycles and colorings
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Rainbow subgraphs in properly edge‐colored graphs
• Rainbow Turán Problems
• Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles
• The prime power conjecture is true for \(n<2,000,000\)

Cited in

(3)

• Colored unavoidable patterns and balanceable graphs
• More on rainbow cliques in edge-colored graphs
• Monochromatic graph decompositions inspired by anti-Ramsey colorings

This page was built for publication: Rainbow subgraphs in edge‐colored complete graphs: Answering two questions by Erdős and Tuza

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6201025)