pith. sign in

arxiv: 1605.09141 · v1 · pith:OPCTLYTSnew · submitted 2016-05-30 · 🧮 math.CO

On edges not in monochromatic copies of a fixed bipartite graph

classification 🧮 math.CO
keywords graphbipartitegraphsnumbercompleteedge-coloringedgesfixed
0
0 comments X
read the original abstract

Let $H$ be a fixed graph. Denote $f(n,H)$ to be the maximum number of edges not contained in any monochromatic copy of $H$ in a 2-edge-coloring of the complete graph $K_n$, and $ex(n,H)$ to be the {\it Tur\'an number} of $H$. An easy lower bound shows $f(n,H)\ge ex(n,H)$ for any $H$ and $n$. In \cite{KS2}, Keevash and Sudakov proved that if $H$ is an edge-color-critical graph or $C_4$, then $f(n,H)= ex(n,H)$ holds for large $n$, and they asked if this equality holds for any graph $H$ when $n$ is sufficiently large. In this paper, we provide an affirmative answer to this problem for an abundant infinite family of bipartite graphs $H$, including all even cycles and complete bipartite graphs $K_{s,t}$ for $t>s^2-3s+3$ or $(s,t)\in\{(3,3),(4,7)\}$. In addition, our proof shows that for all such $H$, the 2-edge-coloring $c$ of $K_n$ achieves the maximum number $f(n,H)$ if and only if one of the color classes in $c$ induces an extremal graph for $ex(n,H)$. We also obtain a multi-coloring generalization for bipartite graphs. Some related problems are discussed in the final section.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.