Homomorfismo em grafos: generalização de conceitos primitivos e aplicação em coloração

Abstract

Let D and F be digraphs. A homomorphism from D to F, denoted by f : D → F, is a function with domain in the vertices of D and codomain in the vertices of F such that #»uv ∈ A(D) ⇒ # » f(u)f(v) ∈ A(F). In this exploratory monograph, a literature review was conducted, concluding that the concept of homomorphism can be used to generalize primitive concepts of graph theory, such as walks, paths, closed walks, cycles, Eulerian trails, Eulerian circuits, isomorphism, automorphism, coloring, and topological sorting. Furthermore, it was found that the class of all digraphs is a quasi-order and, from the definition of the core of a digraph, it is transformed into a partial order on the family of cores C . The concept of classical coloring was redefined as a homomorphism to the complete graph of smallest order in the family K = {K1,K2,K3,...}. Finally, two metrics that refine the Chromatic Number were presented: The Circular Chromatic Number and the Fractional Chromatic Number.