Tópicos em b-continuidade: Operações em Grafos e Grafos Distância-Hereditários
Autores
|
5352 |
Lucas Pierezan Magalhães
|
2419,410
|
|
5353 |
2419,410
|
Informações:
Publicações do PESC
Uma b-coloração de um grafo G é uma coloração dos vértices de G em que cada classe de cor tem um vértice que é adjacente a vértices de cada uma das outras cores. Esse tipo especial de coloração foi introduzido por Irving e Manlove em 1999 coma motivação de que uma coloração que não é uma b-coloração pode ter seu número de cores reduzido.
O número b-cromático χb (G) de um grafo G é o maior k tal que G admite uma b-coloração com k cores. Diferente de outras variações do problema de coloração os valores de k para os quais um grafo admite b-coloração com k cores não constituem necessariamente um intervalo nos inteiros. Dizemos então que G é b-contínuo se este admite b-coloração com k cores para todo k tal que χ(G) ≤ k ≤ χb (G).
Resultados de NP-completude já são conhecidos para o problema de decidir se um grafo é b-contínuo e diversos trabalhos em classes específicas de grafos vem surgindo na literatura. Neste trabalho apresentamos os conceitos básicos sobre b-coloração e resultados relacionados ao problema da b-continuidade. Trabalhamos sobre a perspectiva de operações que preservam b-continuidade e derivamos resultados para algumas classes de grafos, em especial a prova que grafos distância-hereditários são b-contínuos. Para isso, também introduzimos técnicas básicas para a manipulação de b-colorações.
A b-coloring of a graph G is a coloring of the vertices of G such that each color class has a vertex that is adjacent to at least one vertex of each of the other colors. This particular type of coloring was introduced by Irving and Manlove in 1999 with the motivation that a coloring that is not a b-coloring can have its number of colors reduced.
The b-chromatic number χb (G) of a graph G is the maximum number k such that G admits a b-coloring with k colors. Unlike other variations of the coloring problem the values of k for which a graph admits a b-coloring with k colors do not necessarily form an interval in the integers. We say that G is b-continuous if it admits a b-coloring with k colors, for all values of k such that χ(G) ≤ k ≤ χb (G).
NP-completeness results are already known for the problem of deciding whether a graph is b-continuous and several papers on specific graph classes are appearingin the literature. In this work we present the basic concepts on b-colorings and results related to the b-continuity problem. We work on the perspective of graph operations that preserve b-continuity and derive results for some graph classes, in particular we show that the distance-hereditary graphs are b-continuous. For this,
we also introduce basic techniques for manipulating b-colorings.