Local rainbow colorings for various graphs

Xinbu Cheng¹ ; Zixiang Xu²

¹Beijing Normal University
²Extremal Combinatorics and Probability Group, Institute for Basic Science

The electronic journal of combinatorics, Tome 31 (2024) no. 2

Résumé

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: 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)}$. 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$, and $C(n,K_{s,t})=\Omega(n^{2/3})$ for all $t\geqslant s\geqslant 7$. 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 a 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.

Détail

DOI : 10.37236/11911

Classification : 05C15, 05C35, 68R10
Mots-clés : complexity classes, Boolean circuit complexity, combinatorial covering problems