Edge colorings avoiding patterns

Kód výsledku v 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>

Výsledek na webu

<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

—

Jazyk výsledku

angličtina

Název v původním jazyce

Edge colorings avoiding patterns

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Edge colorings avoiding patterns

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/EF16_027%2F0008360" target="_blank" >EF16_027/0008360: Postdoc@MUNI</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2019

Kód důvěrnosti údajů

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

Název periodika

Acta Mathematica Universitatis Comenianae

ISSN

0231-6986

e-ISSN

0862-9544

Svazek periodika

88

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

SK - Slovenská republika

Počet stran výsledku

5

Strana od-do

619-623

Kód UT WoS článku

000484349000041

EID výsledku v databázi Scopus

2-s2.0-85073775473