Sobre coloração total dos grafos r-partidos completos
Resumo
Neste trabalho, investigamos os problemas de coloração total e coloração total equilibrada na família dos grafos r-partidos completos. Provamos que todo grafo bipartido completo Kn,n não possui uma (+1)-coloração total e provamos que todo grafo bipartido completo Kn,m (n > m 1) possui uma ( + 1)-coloração total equilibrada. Além disso, apresentamos uma propriedade de coloração total equilibrada dos grafos r-partidos completos balanceados Krn.
Referências
Behzad, M. (1965). Graphs and their chromatic numbers. PhD thesis, Michigan State University.
Behzad, M., Chartrand, G., and Cooper Jr, J. K. (1967). The colour numbers of complete graphs. J. Lond. Math. Soc., 42:226–228.
Fu, H. L. (1994). Some results on equalized total coloring. Congr. Numer., 102:111–119.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russian Math. Surveys, 23(6):125–141.
Wang, W. F. (2002). Equitable total coloring of graphs with maximum degree 3. Graphs Combin., 18:677–685.
Behzad, M., Chartrand, G., and Cooper Jr, J. K. (1967). The colour numbers of complete graphs. J. Lond. Math. Soc., 42:226–228.
Fu, H. L. (1994). Some results on equalized total coloring. Congr. Numer., 102:111–119.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russian Math. Surveys, 23(6):125–141.
Wang, W. F. (2002). Equitable total coloring of graphs with maximum degree 3. Graphs Combin., 18:677–685.
Publicado
04/07/2016
Como Citar
MARTINS, Raphael; SASAKI, Diana.
Sobre coloração total dos grafos r-partidos completos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 796-799.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2016.9768.
