Famílias Consistentes e a Coloração Total de Grafos
A Teoria dos Grafos é uma área
da Matemática Discreta que permite modelar
e solucionar problemas reais através do
desenvolvimento de algoritmos eficientes.
Este trabalho apresenta um novo conceito,
as Famílias Consistentes, que podem se
juntar a esta Teoria, possibilitando a criação
de modelos que poderão ser aplicados na
resolução de várias situações. Aqui, o objetivo
principal é desenvolver uma heurística para a
coloração total de grafos, procurando respeitar
a conjectura de Vizing. Para isso, definimos
inicialmente alguns termos necessários para
a identificação destas famílias. Em seguida,
provamos quatro proposições relativas a este
novo conceito, e finalizamos o texto fazendo a
conexão entre estas famílias e a coloração total
de grafos.
Famílias Consistentes e a Coloração Total de Grafos
-
DOI: 10.22533/at.ed.4911924057
-
Palavras-chave: Famílias consistentes. Conjectura de Vizing. Coloração total de grafos.
-
Keywords: Consistent Families. Vizing’s conjecture. Total coloring of graphs.
-
Abstract:
The Theory of Graphs is an
area of Discrete Mathematics, which allows
modeling and solving real problems through
the development of efficient algorithms. This
paper presents a new concept, Consistent
Families, which can join to this theory, enabling
the creation of models that can be applicated
in the resolutions of several situations. Here,
the main aim is to develop a heuristic to the
total coloring of graphs, respecting the Vizing’s
conjecture. In order to do it, initially, we defined
some necessary terms for the identification of
these families. After that, we proved four propositions related to this new concept, and
we finished the text by making the connection between these families and the total
coloring of the graph.
-
Número de páginas: 15
- Abel Rodolfo Garcia Lozano
- Angelo Santos Siqueira
- Sérgio Ricardo Pereira de Mattos
- Valessa Leal Lessa de Sá Pinto
