On total coloring of small fullerene nanodiscs

  • Mariana M. F. da Cruz UFRJ
  • Celina M. H. de Figueiredo UFRJ
  • Diana Sasaki UERJ
  • Diane Castonguay UFG

Resumo


We investigate the total coloring of fullerene nanodiscs, a subclass of cubic planar graphs with girth 5 arising in Chemistry, motivated by a conjecture about the nonexistence of a Type 2 cubic graph of girth at least 5. We prove an auxiliary lemma which says that every central layer of a fullerene nanodisc is 4-total colorable, a necessary condition for the nanodisc to be Type 1, and we contribute by giving 4-total colorings for small fullerene nanodiscs, showing that these graphs are Type 1.

Referências

Behzad, M. (1965). Graphs and their chromatic numbers. Michigan State University.

Brinkmann, G., Preissmann, M., and Sasaki, D. (2015). Snarks with total chromatic number 5. Discrete Mathematics and Theoretical Computer Science, 17(1):369–382.

Campos, C. N. (2006). O problema da coloração total em classes de grafos. PhD thesis, University of Campinas, Brazil.

da Cruz, M. (2022). Fullerene Nanodiscs: From Chemistry to Combinatorics. Master’s thesis, COPPE/UFRJ, Rio de Janeiro.

da Cruz, M., de Figueiredo, C., Sasaki, D., and Costa, M. (2021a). Fullerene nanodiscs: from chemistry to combinatorics. In IV Workshop de Pesquisa em Computação dos Campos Gerais (WPCCG 2021).

da Cruz, M., de Figueiredo, C., Sasaki, D., and Costa, M. (2021b). Hunting a type 2 fullerene nanodisc. Matemática Contemporânea, 48:126–136.

Nicodemos, D. (2017). Diâmetro de Grafos Fulerenes e Transversalidade de Ciclos Ímpares de Fuleróides-(3, 4, 5, 6). PhD thesis, Universidade Federal do Rio de Janeiro/COPPE.

Vijayaditya, N. (1971). On total chromatic number of a graph. Journal of the London Mathematical Society, 2:405–408.

Vizing, V. G. (1964). On an estimate of the chromatic class of a p-graph. Discret Analiz, 3:25–30.

Yap, H. P. (1996). Total colourings of graphs. Springer.
Publicado
06/08/2023
CRUZ, Mariana M. F. da; FIGUEIREDO, Celina M. H. de; SASAKI, Diana; CASTONGUAY, Diane. On total coloring of small fullerene nanodiscs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 8. , 2023, João Pessoa/PB. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2023 . p. 15-19. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2023.230129.