A conformabilidade dos grafos subcúbicos conexos
Resumo
Neste artigo, provamos que todo grafo subcúbico conexo $G$ é conformable, exceto se $G$ é o completo $K_4$ ou o bipartido completo $K_{3,3}$. Nossa caracterização conduz a um algoritmo de tempo polinomial.
Referências
Behzad, M. (1965). Graphs and and their chromatic numbers. PhD thesis, Michigan State University.
Brooks, R. L. (1941). On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc., pages 194–197.
Campos, C. N. and de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discrete Appl. Math., pages 585–597.
Chetwynd, A. G. and Hilton, A. J. W. (1988). Some refinements of the total chromatic number conjecture. Congr. Numer., pages 195–216.
Hamilton, G. M., Hilton, A. J. W., and Hind, H. R. F. (1999). Totally critical even order graphs. J. Comb. Theory Ser. B., pages 262–279.
Hilton, A. J. W. and Hind, H. R. (2002). Non-conformable subgraphs of non-conformable graphs. Discrete Math., pages 203–224.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., pages 315–319.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russ. Math. Surv., pages 125–141.
Yap, H. P. (1996). Total colourings of graphs. Springer.
Zorzi, A., Figueiredo, C., Machado, R., Zatesko, L., and Souza, U. (2021). Compositions, decompositions, and conformability for total coloring on power of cycle graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2021.06.012.
Brooks, R. L. (1941). On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc., pages 194–197.
Campos, C. N. and de Mello, C. P. (2007). A result on the total colouring of powers of cycles. Discrete Appl. Math., pages 585–597.
Chetwynd, A. G. and Hilton, A. J. W. (1988). Some refinements of the total chromatic number conjecture. Congr. Numer., pages 195–216.
Hamilton, G. M., Hilton, A. J. W., and Hind, H. R. F. (1999). Totally critical even order graphs. J. Comb. Theory Ser. B., pages 262–279.
Hilton, A. J. W. and Hind, H. R. (2002). Non-conformable subgraphs of non-conformable graphs. Discrete Math., pages 203–224.
Sánchez-Arroyo, A. (1989). Determining the total colouring number is NP-hard. Discrete Math., pages 315–319.
Vizing, V. G. (1968). Some unsolved problems in graph theory. Russ. Math. Surv., pages 125–141.
Yap, H. P. (1996). Total colourings of graphs. Springer.
Zorzi, A., Figueiredo, C., Machado, R., Zatesko, L., and Souza, U. (2021). Compositions, decompositions, and conformability for total coloring on power of cycle graphs. Discrete Appl. Math. https://doi.org/10.1016/j.dam.2021.06.012.
Publicado
31/07/2022
Como Citar
FARIA, Luerbio; NIGRO, Mauro; SASAKI, Diana.
A conformabilidade dos grafos subcúbicos conexos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 49-52.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2022.222744.
