Local rainbow colorings for various graphs

arXiv2207.07532MaRDI QIDQ6405097FDOQ6405097

Authors: Xinbu Cheng, Zixiang Xu 

Publication date: 15 July 2022

Abstract: 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(K_n)$ with $k$ colors, each associated with one of the vertices of $K_n$, such that for every copy $T$ of $H$ in $K_n$, 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: �egin{itemize} item For paths of short length, we show that $C(n,P_4)=Omega(n^{1/5})$ and $C(n,P_t)=Omega(n^{1/3})$ with $tin5,6$, which significantly improve the previously known lower bounds $(logn{)}^{Omega(1)}$. item We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that $C(n,K_r)=Omega(n^{2/3})$ when $rgeqslant8$. This provides the first instance of graph for which the lower bound goes beyond the natural barrier $Omega(n^{1/2})$. Moreover, we prove that $C(n,K_{s,t})=Omega(n^{2/3})$ for $tgeqslantsgeqslant7$. 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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: Local rainbow colorings for various graphs

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