# Complexity of Determining the b-continuity Property of Graphs

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.
Mots-clés :
Document type :
Reports
Domain :
Complete list of metadata

https://hal.inria.fr/inria-00099781
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 9:41:08 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM

### Identifiers

• HAL Id : inria-00099781, version 1

### Citation

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⟩

Record views