Color isomorphic even cycles and a related Ramsey problem

Abstract

In this paper, we first study a new extremal problem recently posed by Conlon and Tyomkyn~(arXiv: 2002.00921). Given a graph $H$ and an integer $k⩾2$, let $f_k(n,H)$ be the smallest number of colors $c$ such that there exists a proper edge-coloring of the complete graph $K_n$ with $c$ colors containing no $k$ vertex-disjoint color-isomorphic copies of $H$. Using algebraic properties of polynomials over finite fields, we give an explicit proper edge-coloring of $K_n$ and show that $f_k(n,C_4)=\Theta (n)$ when $k⩾3$ and $n\to \infty$. The methods we used in the edge-coloring may be of some independent interest. We also consider a related generalized Ramsey problem. For given graphs $G$ and $H,$ let $r(G,H,q)$ be the minimum number of edge-colors (not necessarily proper) of $G$, such that the edges of every copy of $H\subseteq G$ together receive at least $q$ distinct colors. Establishing the relation to the Turán number of specified bipartite graphs, we obtain some general lower bounds for $r(K_{n,n},K_{s,t},q)$ with a broad range of $q$.

13 pages, accepted by SIAM Journal on Discrete Mathematics