Edge colorings avoiding patterns
| Autoři | |
|---|---|
| Rok publikování | 2019 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | Acta Mathematica Universitatis Comenianae |
| Fakulta / Pracoviště MU | |
| Citace | |
| www | http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200/702 |
| Klíčová slova | edge coloring; entropy compression |
| Přiložené soubory | |
| Popis | 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. |
| Související projekty: |