Distance-two coloring of sparse graphs

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Distance-two coloring of sparse graphs
Original language description
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
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
<a href="/en/project/LL1201" target="_blank" >LL1201: Complex Structures: Regularities in Combinatorics and Discrete Mathematics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)