%A Dębski, Michał Karol
%D 2019
%T Edge colorings avoiding patterns
%K
%X 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.
%U http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200
%J Acta Mathematica Universitatis Comenianae
%0 Journal Article
%P 619-623%V 88
%N 3
%@ 0862-9544
%8 2019-07-29