Back to Search
Start Over
The b-Continuity of Graphs with Large Girth.
- Source :
-
Graphs & Combinatorics . Sep2017, Vol. 33 Issue 5, p1139-1146. 8p. - Publication Year :
- 2017
-
Abstract
- A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer $$b(G)$$ for which G has a b-coloring with $$b(G)$$ colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval $$[\chi (G),b(G)]$$ . It is known that not all graphs are b-continuous, and that it is NP-complete to decide whether a given graph G is b-continuous even if $$\chi (G)$$ and $$b(G)$$ are known. Also, there are many results that show that finding b-colorings of graphs with large girth is an easier task. For instance, finding $$b(G)$$ can be done in polynomial time when G has girth at least 7; also, regular graphs with girth at least 8 are b-continuous. In this article, we show that if G has girth at least 10, then G is b-continuous. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 09110119
- Volume :
- 33
- Issue :
- 5
- Database :
- Academic Search Index
- Journal :
- Graphs & Combinatorics
- Publication Type :
- Academic Journal
- Accession number :
- 125801522
- Full Text :
- https://doi.org/10.1007/s00373-017-1828-x