Um estudo sobre emparelhamentos e a coloração total
Resumo
Neste trabalho, investigamos a relação entre emparelhamentos e coloração total de grafos e provamos que todos os membros de uma família infinita de grafos de Petersen generalizados são Tipo 1.
Palavras-chave:
Teoria dos grafos, emparelhamentos, coloração total
Referências
Behzad, M. (1965). Graphs and their chromatic numbers. PhD thesis, Michigan State University.
Campos, C. N. (2006). O Problema da Coloração Total em Classes de Grafos. Tese de Doutorado, Univesidade Estadual de Campinas, São Paulo.
Petersen, J. (1891). Die theorie der regulären graphen (em alemão). Acta Math., v. 15, pages 193-220.
Rosenfeld, M. (1971). On the total coloring of certain graphs. Israel J. Math., pages 396–402.
Sasaki, D. (2013). Sobre Coloração Total de Grafos Cúbicos. Tese de Doutorado, Universidade Federal do Rio de Janeiro, Rio de Janeiro.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math, pages 315–319.
Vijayaditya, N. (1971). On total chromatic number of a graph. J. London Math., pages 405–408.
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., v. 3, pages 25–30.
Yap, H. (1996). Total Colourings of Graphs. Springer Publishing Company Incorporated.
Campos, C. N. (2006). O Problema da Coloração Total em Classes de Grafos. Tese de Doutorado, Univesidade Estadual de Campinas, São Paulo.
Petersen, J. (1891). Die theorie der regulären graphen (em alemão). Acta Math., v. 15, pages 193-220.
Rosenfeld, M. (1971). On the total coloring of certain graphs. Israel J. Math., pages 396–402.
Sasaki, D. (2013). Sobre Coloração Total de Grafos Cúbicos. Tese de Doutorado, Universidade Federal do Rio de Janeiro, Rio de Janeiro.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math, pages 315–319.
Vijayaditya, N. (1971). On total chromatic number of a graph. J. London Math., pages 405–408.
Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Metody Diskret. Analiz., v. 3, pages 25–30.
Yap, H. (1996). Total Colourings of Graphs. Springer Publishing Company Incorporated.
Publicado
31/07/2022
Como Citar
FUSQUINO, Sérgio; NIGRO, Mauro; SASAKI, Diana; BORCHERT, Ingrid.
Um estudo sobre emparelhamentos e a coloração total. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 25-28.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222599.
