About: Distance-two coloring of sparse graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Distance-two coloring of sparse graphs Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
rdfs:seeAlso	http://dx.doi.org/10.1016/j.ejc.2013.09.002
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 obvious lower 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-dense classes. 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 obvious lower 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-dense classes. (en)
Title	Distance-two coloring of sparse graphs Distance-two coloring of sparse graphs (en)
skos:prefLabel	Distance-two coloring of sparse graphs Distance-two coloring of sparse graphs (en)
skos:notation	RIV/00216208:11320/14:10283287!RIV15-MSM-11320___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(LL1201)
http://linked.open...iv/cisloPeriodika	únor
http://linked.open...vai/riv/dodaniDat	2015
http://linked.open...aciTvurceVysledku	Dvořák, Zdeněk
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	11797
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/14:10283287
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	number; grad; bounded expansion (en)
http://linked.open.../riv/klicoveSlovo	number bounded expansion grad
http://linked.open...odStatuVydavatele	GB - Spojené království Velké Británie a Severního Irska
http://linked.open...ontrolniKodProRIV	[6898B203C07A]
http://linked.open...i/riv/nazevZdroje	European Journal of Combinatorics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Complex Structures: Regularities in Combinatorics and Discrete Mathematics
http://linked.open...UplatneniVysledku	2014
http://linked.open...v/svazekPeriodika	36
http://linked.open...iv/tvurceVysledku	Dvořák, Zdeněk Esperet, Louis
http://linked.open...ain/vavai/riv/wos	000328869800036
issn	0195-6698
number of pages	10 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.ejc.2013.09.002
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software