b-Colorações e colorações de Nash em grafos de cintura

Abstract

In this dissertation we study two variations in the coloring of graphs, b-colorings and Nash colorings. A b-coloring of a graph G is a coloring f : V(G) → {1,...,k} such that for each i ∈{1,...,k} there is a vertex v ∈V(G) such that f (N[v]) = {1,...,k}. A Nash coloring is a coloring f : V(G) → {1,...,k} such that every vertex v ∈ f −1 (i) has a neighboor in f−1 ( j) for any i, j such that | f−1( j)| ≥ | f−1(i)|. The b-chromatic number( Nash number), denoted by b(G)(Nn(G)), of a graph is the largest integer such that the graph has a b-coloring( Nash coloring) with such integer of colors. The b-spectrum( Nash spectrum) of a graph is the set of integers k such that the graph has a b-coloring( Nash coloring) using k colors. A graph G is b-continuous( Nash continuous) when its b-spectrum( Nash spectrum) is the set [χ(G),b(G)]∩ Z ([χ(G),Nn(G)]∩ Z ). We started with b-colorings. Where we improove the previus result in literature that states that every graph with girth at least 10 is b-continuous. We show the same thesis holds when the graph has girht at least 8. Moreover we show that if a graph G has girth at least 7, then its b-spectrum contains the set [2χ(G),b(G)]. Regarding the Nash colorings, we demonstrate many properties of this coloring and its resemblance with the b-coloring. We show graphs that are not Nash continuous. Moreover, we prove that every tree, T, has the Nash number at least Γ(T)−1 and that every tree is Nash continuous.