Edge colorings avoiding patterns

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F19%3A00112695" target="_blank" >RIV/00216224:14330/19:00112695 - isvavai.cz</a>
Result on the web
<a href="http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200/702" target="_blank" >http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1200/702</a>
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Edge colorings avoiding patterns
Original language 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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/EF16_027%2F0008360" target="_blank" >EF16_027/0008360: Postdoc@MUNI</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)