The b-continuity of graphs with large girth
Abstract
A b-coloring of a graph is a proper coloring such that each color class has at least one vertex which is adjacent to each other color class. The b-spectrum of G is the set Sb(G) of integers k such G has a b-coloring with k colors and b(G) = maxSb(G) is the b-chromatic number of G. A graph is b-continous if Sb(G) = |X(G), b(G)| ∩ Z. An infinite number of graphs that are not b-continuous is known. Also it is known that graphs with girth at least 10 are b-continuous. In this article, we prove that graphs with girth at least 8 are b-continuous and that the b-spectrum of graphs with girth at least 7 contains the integers between 2X(G) and b(G).
References
Balakarishnan, R. and Kavaskar, T. (2012). b-coloring of kneser graphs. Discrete Applied Mathematics, 160:9–14.
Barth, D., Cohen, J., and Faik, T. (2007). On the b-continuity property of graphs. Discrete Applied Mathematics, 155:1761–1768.
Bondy, J. and Murty, U. (2008). Graph Theory. Springer.
Campos, V., Lima, C., and Silva, A. (2015). Graphs of girth at least 7 have high bchromatic number. European Journal of Combinatorics, 48:154–164.
Irving, R. W. and Manlove, D. (1999). The b-chromatic number of a graph. Discrete Applied Mathematics, 91:127–141.
Kratochvíl, J., Tuza, Z., and Voigt, M. (2002). On the b-chromatic number of graphs. In Goos, G., Hartmanis, J., van Leeuwen, J., and Kučera, L., editors, Graph-Theoretic Concepts in Computer Science, pages 310–320. Springer Berlin Heidelberg.
Lozin, V. and Kaminski, M. (2007). Coloring edges and vertices of graphs without short or long cycles. Contributions do Discrete Mathematics, 2.
Sales, C. L. and Silva, A. (2017). The b-continuity of graphs with large girth. Graphs and Combinatorics, 33:1138–1146.
Barth, D., Cohen, J., and Faik, T. (2007). On the b-continuity property of graphs. Discrete Applied Mathematics, 155:1761–1768.
Bondy, J. and Murty, U. (2008). Graph Theory. Springer.
Campos, V., Lima, C., and Silva, A. (2015). Graphs of girth at least 7 have high bchromatic number. European Journal of Combinatorics, 48:154–164.
Irving, R. W. and Manlove, D. (1999). The b-chromatic number of a graph. Discrete Applied Mathematics, 91:127–141.
Kratochvíl, J., Tuza, Z., and Voigt, M. (2002). On the b-chromatic number of graphs. In Goos, G., Hartmanis, J., van Leeuwen, J., and Kučera, L., editors, Graph-Theoretic Concepts in Computer Science, pages 310–320. Springer Berlin Heidelberg.
Lozin, V. and Kaminski, M. (2007). Coloring edges and vertices of graphs without short or long cycles. Contributions do Discrete Mathematics, 2.
Sales, C. L. and Silva, A. (2017). The b-continuity of graphs with large girth. Graphs and Combinatorics, 33:1138–1146.
Published
2018-07-26
How to Cite
IBIAPINA, Allen; SILVA, Ana.
The b-continuity of graphs with large girth. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 25-28.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3143.
