HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:41:08 AM
Last modification on : Friday, February 26, 2021 - 3:28:02 PM


  • 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⟩



Record views