A b-continuidade de grafos com cintura alta⇤.

  • Allen Ibiapina
  • Ana Silva

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 Sb(G) dos inteiros k tais que G tem uma b-coloraçao com k cores e b(G) = max Sb(G) é o número b-cromático de G. Um grafo é b-contínuo se Sb(G) = [ (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 bespectro de grafos com cintura pelo menos 7 contém os inteiros entre 2 (G) e b(G).

Publicado
26/07/2018
IBIAPINA, Allen; SILVA, Ana. A b-continuidade de grafos com cintura alta⇤.. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 3. , 2018, Natal. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2018 . ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2018.3143.