Geodesic
List circular backbone colouring
Discrete mathematics & theoretical computer science, Tome 16 (2014) no. 1.

Voir la notice de l'article provenant de la source Episciences

A natural generalization of graph colouring involves taking colours from a metric space and insisting that the endpoints of an edge receive colours separated by a minimum distance dictated by properties of the edge. In the q-backbone colouring problem, these minimum distances are either q or 1, depending on whether or not the edge is in the backbone. In this paper we consider the list version of this problem, with particular focus on colours in ℤp - this problem is closely related to the problem of circular choosability. We first prove that the list circular q-backbone chromatic number of a graph is bounded by a function of the list chromatic number. We then consider the more general problem in which each edge is assigned an individual distance between its endpoints, and provide bounds using the Combinatorial Nullstellensatz. Through this result and through structural approaches, we achieve good bounds when both the graph and the backbone belong to restricted families of graphs. 
@article{DMTCS_2014_16_1_a1,
     author = {Havet, Frederic and King, Andrew D.},
     title = {List circular backbone colouring},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {16},
     number = {1},
     year = {2014},
     doi = {10.46298/dmtcs.639},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.639/}
}
TY  - JOUR
AU  - Havet, Frederic
AU  - King, Andrew D.
TI  - List circular backbone colouring
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - 16
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.639/
DO  - 10.46298/dmtcs.639
LA  - en
ID  - DMTCS_2014_16_1_a1
ER  - 
%0 Journal Article
%A Havet, Frederic
%A King, Andrew D.
%T List circular backbone colouring
%J Discrete mathematics & theoretical computer science
%D 2014
%V 16
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.639/
%R 10.46298/dmtcs.639
%G en
%F DMTCS_2014_16_1_a1
Havet, Frederic; King, Andrew D. List circular backbone colouring. Discrete mathematics & theoretical computer science, Tome 16 (2014) no. 1. doi : 10.46298/dmtcs.639. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.639/

Cité par Sources :