A b-continuidade de grafos com cintura alta

• Allen Ibiapina
• Ana Silva

DOI: https://doi.org/10.5753/etc.2018.3143

Resumo

Uma b-coloração de um grafo é uma coloração própria, tal que cada classe de cor possui um vértice que é vizinho de pelo menos um vértice das outras classes de cores. O b-espectro de G é o conjunto S_b(G) dos inteiros k tais que G tem uma b-coloraçao com k cores e b(G) = max S_b(G) é o número b-cromático de G. Um grafo é b-contínuo se S_b(G) = |X(G), b(G)| ∩ Z. É conhecida uma infinidade de grafos que não são b-contínuos. Também é sabido que grafos com cintura maior ou igual a 10 são b-contínuos. Neste artigo, mostramos que grafos com cintura pelo menos 8 são b-contínuos e que o b-espectro de grafos com cintura pelo menos 7 contém os inteiros entre 2X(G) e b(G).

Referências

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.