A study on matchings and total colorings
Abstract
In this paper, we investigate the relationship between matchings and total coloring of graphs and prove that all members of an infinite family of generalized Petersen graphs are Type 1.
Keywords:
Graph theory, matchings, total coloring
References
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.
Published
2022-07-31
How to Cite
FUSQUINO, Sérgio; NIGRO, Mauro; SASAKI, Diana; BORCHERT, Ingrid.
A study on matchings and total colorings. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (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.
