Distance-two coloring of sparse graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10283287" target="_blank" >RIV/00216208:11320/14:10283287 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Distance-two coloring of sparse graphs

Popis výsledku v původním jazyce

Consider a graph G = (V, E) and, for each vertex v is an element of V. a subset Sigma(v) of neighbors of v. A Sigma-coloring is a coloring of the elements of V so that vertices appearing together in some E(v) receive pairwise distinct colors. An obviouslower bound for the minimum number of colors in such a coloring is the maximum size of a set Sigma(v), denoted by rho(Sigma). In this paper we study graph classes F for which there is a function f, such that for any graph G is an element of F and any Sigma, there is a Sigma-coloring using at most f (rho(Sigma)) colors. It is proved that if such a function exists for a class F, then f can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-d

Název v anglickém jazyce

Distance-two coloring of sparse graphs

Popis výsledku anglicky

Consider a graph G = (V, E) and, for each vertex v is an element of V. a subset Sigma(v) of neighbors of v. A Sigma-coloring is a coloring of the elements of V so that vertices appearing together in some E(v) receive pairwise distinct colors. An obviouslower bound for the minimum number of colors in such a coloring is the maximum size of a set Sigma(v), denoted by rho(Sigma). In this paper we study graph classes F for which there is a function f, such that for any graph G is an element of F and any Sigma, there is a Sigma-coloring using at most f (rho(Sigma)) colors. It is proved that if such a function exists for a class F, then f can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-d

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/LL1201" target="_blank" >LL1201: Komplexní Struktury: Regularita v Kombinatorice a Diskrétní Matematice</a><br>

Návaznosti

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

Rok uplatnění

2014

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

36

Číslo periodika v rámci svazku

únor

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

10

Strana od-do

406-415

Kód UT WoS článku

000328869800036

EID výsledku v databázi Scopus

—