Large subgraphs in rainbow-triangle free colorings

DOI10.1002/JGT.22117zbMATH Open1370.05073arXiv1612.00471OpenAlexW2963155030MaRDI QIDQ5360880FDOQ5360880

Authors: Adam Zsolt Wagner 

Publication date: 26 September 2017

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

Abstract: Fox--Grinshpun--Pach showed that every $3$-coloring of the complete graph on $n$ vertices without a rainbow triangle contains a clique of size $Omegaleft(n^{1/3}lo{g}^{2}night)$ which uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a $2$-colored subgraph with chromatic number at least $n^{2/3}$, and this is best possible. We further show that for fixed positive integers $s,r$ with $sleqr$, every $r$-coloring of the edges of the complete graph on $n$ vertices without a rainbow triangle contains a subgraph that uses at most $s$ colors and has chromatic number at least $n^{s/r}$, and this is best possible. Fox--Grinshpun--Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalisation of the celebrated theorem of ErdH{o}s-Szekeres, which states that any sequence of $n$ numbers contains a monotone subsequence of length at least $sqrtn$. We prove that if an $r$-coloring of the edges of an $n$-vertex tournament does not contain a rainbow triangle then there is an $s$-colored directed path on $n^{s/r}$ vertices, which is best possible. This gives a partial answer to a question of Loh.

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

Recommendations

• The Erdős-Hajnal conjecture for rainbow triangles
• Rainbow triangles and cliques in edge-colored graphs
• scientific article
• On graphs with a large number of edge-colorings avoiding a rainbow triangle
• Note on rainbow triangles in edge-colored graphs

zbMATH Keywords

chromatic numberGallai coloringrainbow triangleErdős-Szekeres theorem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cited In (5)

• Monochromatic stars in rainbow \(K_3\)-free and \(S_3^+\)-free colorings
• Subgraphs with a large cochromatic number
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Forbidden rainbow subgraphs that force large monochromatic or multicolored \(k\)-connected subgraphs
• The length of an s-increasing sequence of r-tuples

This page was built for publication: Large subgraphs in rainbow-triangle free colorings

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