Coloração geodésica de gráficos

Um subconjunto de vértices S de um grafo G = (V,E) é chamado de conjunto geodésico se todo vértice em V −S está em alguma geodésica entre quaisquer dois vértices em S. A cardinalidade mínima de um conjunto geodésico de G é chamada de número geodésico de G e é denotada por g(G). Uma coloração geodésica de um grafo G é uma coloração própria de vértices de G na qual cada vértice em pelo menos um conjunto geodésico de G recebe uma cor diferente. O número mínimo de cores usadas em uma coloração geodésica de G é chamado de número cromático geodésico de G e é denotado por χg(G). Neste artigo, realizamos um estudo detalhado de χg(G), apresentando resultados de existência, limites em relação a outros parâmetros de grafos e caracterizações de grafos para os quais χg(G) = 2 e χg(G) = n, onde n é a ordem do grafo. Além disso, provamos que para toda árvore T, χg(T) é igual ao número de vértices pendentes em T, a menos que T seja uma estrela ou um caminho com um número ímpar de vértices.