Edge colorings avoiding patterns*

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F24%3A00139279" target="_blank" >RIV/00216224:14330/24:00139279 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.ejc.2023.103822" target="_blank" >https://doi.org/10.1016/j.ejc.2023.103822</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2023.103825" target="_blank" >10.1016/j.ejc.2023.103825</a>

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 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 a constant C such that every graph with maximum degree increment admits an edge coloring with C increment colors avoiding P; the same also holds for infinite sets of such patterns, provided that the number of patterns in the set grows at most exponentially. (c) 2023 Elsevier Ltd. All rights reserved.

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 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 a constant C such that every graph with maximum degree increment admits an edge coloring with C increment colors avoiding P; the same also holds for infinite sets of such patterns, provided that the number of patterns in the set grows at most exponentially. (c) 2023 Elsevier Ltd. All rights reserved.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

117

Číslo periodika v rámci svazku

103825

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

9

Strana od-do

1-9

Kód UT WoS článku

001164962900001

EID výsledku v databázi Scopus

2-s2.0-85171984112