2022/07/15 by Xinbu Cheng, Zixiang Xu, Cheng, Xinbu +1
Computer Science · Mathematics · #05C15 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2207.07532
openalex publication_date 2022/07/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Motivated by a problem in theoretical computer science suggested by Wigderson, Alon and Ben-Eliezer studied the following extremal problem systematically one decade ago. Given a graph H, let C(n,H) be the minimum number k such that the following holds. There are n colorings of E(Kn) with k colors, each associated with one of the vertices of Kn, such that for every copy T of H in Kn, at least one of the colorings that are associated with V(T) assigns distinct colors to all the edges of E(T). In this paper, we obtain several new results in this problem including: \beginitemize \item For paths of short length, we show that C(n,P4)=Ω(n1/5) and C(n,Pt)=Ω(n1/3) with t∈\5,6\, which significantly improve the previously known lower bounds (logn)Ω(1). \item We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that C(n,Kr)=Ω(n2/3) when r\geqslant 8. This provides the first instance of graph for which the lower bound goes beyond the natural barrier Ω(n1/2). Moreover, we prove that C(n,Ks,t)=Ω(n2/3) for t\geqslant s\geqslant 7. \item When H is a star with at least 4 leaves, a matching of size at least 4, or a path of length at least 7, we give the new lower bound for C(n,H). We also show that for any graph H with at least 6 edges, C(n,H) is polynomial in n. All of these improve the corresponding results obtained by Alon and Ben-Eliezer.