Edge colorings avoiding patterns

Abstract

We say that a pattern is a graph together with an edge coloring, and a pattern $P=(H,c)$ occurs in some edge coloring $c'$ of $G$ if $c'$, restricted to some subgraph of $G$ isomorphic to $H$, is equal to $c$ up to renaming the colors. Inspired by Matou\v{s}ek's visibility blocking problem, we study edge colorings of cliques that avoid certain patterns.
We show that for every pattern $P$, such that the number of edges in $P$ is at least the number of vertices in $P$ plus the number of colors minus $2$, there is an edge coloring of $K_n$ that avoids $P$ and uses linear number of colors; the same also holds for finite sets of such patterns.