Edge colorings avoiding patterns

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

DĘBSKI Michał Karol

Rok publikování 2019
Druh Článek v odborném periodiku
Časopis / Zdroj Acta Mathematica Universitatis Comenianae
Fakulta / Pracoviště MU

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info