Edge colorings avoiding patterns

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

DĘBSKI Michał Karol

Year of publication 2019
Type Article in Periodical
Magazine / Source Acta Mathematica Universitatis Comenianae
MU Faculty or unit

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.