Edge colorings avoiding patterns
| Authors | |
|---|---|
| Year of publication | 2019 |
| Type | Article in Periodical |
| Magazine / Source | Acta Mathematica Universitatis Comenianae |
| MU Faculty or unit | |
| Citation | |
| Web | http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200/702 |
| Keywords | edge coloring; entropy compression |
| Attached files | |
| Description | 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 Matousek'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. |
| Related projects: |