# Edge colorings avoiding patterns

## Main Article Content

## 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.

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
Issue

Section

EUROCOMB 2019