Complexity of Determining the b-continuity Property of Graphs

Dominique Barth Johanne Cohen 1 Faik Taoufik
1 ALGORILLE - Algorithms for the Grid
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper deals with b-colorings of a graph $G$, i.e., proper colorings in which for each color, there exists at least one vertex it is assigned to such that each other color is assigned to at least one of its neighboor. The maximal cardinality of such a $b$-coloring is denoted by $b(G)$, and each proper coloring with cardinal $\xi(G)$ is a $b$-coloring. We say that $G$ is b-continuous iff for each $k$, $\xi(G) \leq k \leq b(G)$, there exists a b-coloring with cardinal $k$. It is well known that no all graphs are $b$-continuous. Calling $b$-spectrum of $G$ the set of cardinals of all the b-colorings of $G$, we first show that for any integer set $I$, there exists a graph which $b$-spectrum is $I$. Then, we show that, even if $b$-coloring s of cardinal $\xi(G)$ and $b(G)$ are given, the problem of knowing if $G$ is $b $-continuous is NP-complete. At end, we show that interval graphs are $b$-continuous.
Type de document :
[Intern report] A03-R-519 || barth03c, 2003, 11 p
Liste complète des métadonnées
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 09:41:08
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48


  • HAL Id : inria-00099781, version 1



Dominique Barth, Johanne Cohen, Faik Taoufik. Complexity of Determining the b-continuity Property of Graphs. [Intern report] A03-R-519 || barth03c, 2003, 11 p. 〈inria-00099781〉



Consultations de la notice