Can I read Local Rainbow Colorings for Various Graphs on EtoBox?

Local Rainbow Colorings for Various Graphs by Cheng, Xinbu; Xu, Zixiang is a scholarly article available to read on EtoBox.

What is Local Rainbow Colorings for Various Graphs about?

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: \begin{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 $t\in\{5,6\}$, which significantly improve the previously known lower bounds $(\log{n})^{\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 $r\geqslant 8$. 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 $t\geqslant s\geqslant 7$.

Author

Cheng, Xinbu; Xu, Zixiang

Published

2022

Language

EN