Edge colorings avoiding patterns

Main Article Content

Michał Karol Dębski


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.

Article Details

How to Cite
Dębski, M. (2019). Edge colorings avoiding patterns. Acta Mathematica Universitatis Comenianae, 88(3), 619-623. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200/702