Rainbow triangles and cliques in edge-colored graphs
From MaRDI portal
Publication:2011150
DOI10.1016/J.EJC.2019.103037zbMATH Open1428.05102arXiv1810.04980OpenAlexW2980821823MaRDI QIDQ2011150FDOQ2011150
Authors: Stefan Ehard, Elena Mohr 
Publication date: 28 November 2019
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Abstract: For an edge-colored graph, a subgraph is called rainbow if all its edges have distinct colors. We show that if is an edge-colored graph of order and size using colors on its edges, and for a non-negative integer , then contains at least rainbow triangles. For , we show that this result is best possible, and we completely characterize the class of edge-colored graphs for which this result is sharp. Furthermore, we show that an edge-colored graph contains at least rainbow triangles if where denotes the number of distinct colors incident to a vertex . Finally we characterize the edge-colored graphs without a rainbow clique of size at least six that maximize the sum of edges and colors . Our results answer two questions of Fujita, Ning, Xu and Zhang [On sufficient conditions for rainbow cycles in edge-colored graph, arXiv:1705.03675, 2017]
Full work available at URL: https://arxiv.org/abs/1810.04980
Recommendations
Cites Work
- Rainbow triangles in edge-colored graphs
- Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
- Rainbow numbers for matchings and complete graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An anti-Ramsey theorem
- On a theorem of Rademacher-Turán
- Title not available (Why is that?)
- On sufficient conditions for rainbow cycles in edge-colored graphs
- Rainbow cliques in edge-colored graphs
Cited In (32)
- Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
- Density of Gallai multigraphs
- Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs
- Rainbow clique subdivisions
- Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
- Disjoint color-avoiding triangles
- Large subgraphs in rainbow-triangle free colorings
- Vertex-disjoint rainbow triangles in edge-colored graphs
- On a colored Turán problem of Diwan and Mubayi
- On colorful edge triples in edge-colored complete graphs
- Vertex-disjoint rainbow cycles in edge-colored graphs
- Rainbow cliques in edge-colored graphs
- Rainbow triangles in arc-colored tournaments
- Rainbow Turán number of clique subdivisions
- A rainbow version of Mantel's theorem
- Rainbow triangles in edge-colored graphs
- Extremal results for graphs avoiding a rainbow subgraph
- Rainbow triangles in edge-colored Kneser graphs
- Rainbow subdivisions of cliques
- Color degree sum conditions for rainbow triangles in edge-colored graphs
- Counting rainbow triangles in edge-colored graphs
- More on rainbow cliques in edge-colored graphs
- Rainbow triangles in three-colored graphs
- Title not available (Why is that?)
- Edge-disjoint rainbow triangles in edge-colored graphs
- Rainbow edge-pancyclicity of strongly edge-colored graphs
- Rainbow edge-coloring and rainbow domination
- Disproof of a conjecture on the rainbow triangles in arc-colored digraphs
- Note on rainbow triangles in edge-colored graphs
- Rainbow triangles in arc-colored digraphs
- On graphs with a large number of edge-colorings avoiding a rainbow triangle
- The Erdős-Faber-Lovász conjecture revisited
This page was built for publication: Rainbow triangles and cliques in edge-colored graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2011150)
