Rainbow triangles and cliques in edge-colored graphs

DOI10.1016/J.EJC.2019.103037MaRDI QIDQ2011150zbMATH OpenOpenAlexFDO

Authors Stefan Ehard, Elena Mohr

Publication date 28 November 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

edge-colored graphrainbow cyclecolor neighborhoodminimum color degree

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: For an edge-colored graph, a subgraph is called rainbow if all its edges have distinct colors. We show that if $G$ is an edge-colored graph of order $n$ and size $m$ using $c$ colors on its edges, and $$ for a non-negative integer $k$, then $G$ contains at least $k$ rainbow triangles. For $ngeq3k$, 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 $G$ contains at least $k$ rainbow triangles if $$ where $d_G^c(v)$ denotes the number of distinct colors incident to a vertex $v$. Finally we characterize the edge-colored graphs without a rainbow clique of size at least six that maximize the sum of edges and colors $m+c$. 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]

Recommendations

• Edge-disjoint rainbow triangles in edge-colored graphs
• Rainbow triangles in edge-colored graphs
• Note on rainbow triangles in edge-colored graphs
• Rainbow cliques in edge-colored graphs
• Color degree sum conditions for rainbow triangles in edge-colored graphs

Cites work

• scientific article; zbMATH DE number 3821782 (Why is no real title available?)
• scientific article; zbMATH DE number 3494450 (Why is no real title available?)
• scientific article; zbMATH DE number 3529891 (Why is no real title available?)
• scientific article; zbMATH DE number 3188526 (Why is no real title available?)
• An anti-Ramsey theorem
• On a theorem of Rademacher-Turán
• On sufficient conditions for rainbow cycles in edge-colored graphs
• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Rainbow cliques in edge-colored graphs
• Rainbow numbers for matchings and complete graphs
• Rainbow triangles in edge-colored graphs

Cited in

(32)

• The Erdős-Faber-Lovász conjecture revisited
• Rainbow \(C_3\)'s and \(C_4\)'s in edge-colored graphs
• Density of Gallai multigraphs
• Sufficient conditions for properly colored \(C_3\)'s and \(C_4\)'s in edge-colored complete graphs
• Proper cycles and rainbow cycles in 2-triangle-free edge-colored complete graphs
• Rainbow clique subdivisions
• 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 triangles in arc-colored tournaments
• Rainbow Turán number of clique subdivisions
• Rainbow cliques in edge-colored graphs
• Rainbow triangles in edge-colored graphs
• A rainbow version of Mantel's theorem
• Rainbow triangles in edge-colored Kneser graphs
• Extremal results for graphs avoiding a rainbow subgraph
• Color degree sum conditions for rainbow triangles in edge-colored graphs
• Rainbow subdivisions of cliques
• Counting rainbow triangles in edge-colored graphs
• More on rainbow cliques in edge-colored graphs
• Rainbow triangles in three-colored graphs
• scientific article; zbMATH DE number 434896 (Why is no real title available?)
• Edge-disjoint rainbow triangles in edge-colored graphs
• Rainbow edge-coloring and rainbow domination
• Rainbow edge-pancyclicity of strongly edge-colored graphs
• 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

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)