2020/04/04 by Zixiang Xu, Xu, Zixiang, Tao Zhang +5
Computer Science · Mathematics · #05C15 #05C35 #11T06 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2004.01932
openalex publication_date 2020/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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\geqslant 2, let fk(n,H) be the smallest number of colors c such that there exists a proper edge-coloring of the complete graph Kn 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 Kn and show that fk(n, C4)=Θ(n) when k\geqslant 3 and n→∞. 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⊆ 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(Kn,n,Ks,t,q) with a broad range of q.