Celina Miraglia Herrera de Figueiredo

Landmarks are important and yet hard to celebrate. We have the privilege of witnessing Jayme Luiz Szwarcfiter reach 48 supervised doctoral theses as we celebrate the 50th anniversary of his own doctoral degree. The past five decades have witnessed the birth and growth of a vibrant research community on Graphs and Algorithms in Brazil, covering both the diversity of themes and the diversity of regions of our continental country. Jayme has acted as a key catalyst in articulating collaborations beyond the regions of Brazil to reach Argentina, Mexico, and Chile. He has fostered regional and international collaboration and helped consolidate different research groups in Latin America. On this landmark occasion, we describe some of the noteworthy achievements of our community, with special attention to Professor Szwarcfiter's role.

Snarks are cubic graphs with peculiar properties, making them relevant to several problems in graph theory, such as edge and total coloring. While infinite families of Type 1 snarks are well known, Type 2 snarks remain rare and difficult to construct. In 1996, Kochol introduced a method for constructing new snarks by combining two known snarks, usually Type 1. We apply Kochol’s superposition to obtain new Type 2 snarks. As a result, we construct an infinite family of Type 2 snarks with girth 4 by Kochol’s superposition of a known Type 2 snark with the infinite family of Goldberg snarks.

The coloring game is a two-player non-cooperative game conceived in 1981. Alice and Bob alternate turns to properly color the vertices of a finite graph G with t colors. Alice’s goal is to properly color the vertices of G with t colors; Bob’s aim is to prevent it. If, at any point, there is an uncolored vertex without an available color, Bob wins; otherwise, Alice wins. The game chromatic number χg(G) is the smallest t for Alice to have a winning strategy. In 1991, Bodlaender showed that a caterpillar was the smallest tree T with χg(T) = 4; in 1993, Faigle et al. proved χg(T) ≤ 4 for every tree T. In 2015, Dunn et al. proposed the characterization of forests with game chromatic numbers 3 and 4. In this paper, we extend results from caterpillars to more general trees, and establish sufficient conditions to ensure that a tree has game chromatic number 4.

A total coloring of a graph colors all its elements, vertices and edges, with no adjacency conflicts. The Total Coloring Conjecture (TCC) is a sixty year old challenge, says that every graph admits a total coloring with at most maximum degree plus two colors, and many graph parameters have been studied in connection with its validity. If a graph admits a total coloring with maximum degree plus one colors, then it is Type 1, whereas it is Type 2, in case it does not admit a total coloring with maximum degree plus one colors but it does satisfy the TCC. Cavicchioli, Murgolo and Ruini proposed in 2003 the hunting for a Type 2 snark with girth at least 5. Brinkmann, Preissmann and Sasaki in 2015 conjectured that there is no Type 2 cubic graph with girth at least 5. We investigate the total coloring of fullerene nanodiscs, a class of cubic planar graphs with girth 5 arising in Chemistry. We prove that the central layer of an arbitrary fullerene nanodisc is 4-total colorable, a necessary condition for the nanodisc to be Type 1. We extend the obtained 4-total coloring to a 4-total coloring of the whole nanodisc, when the radius satisfies r = 5 + 3k, providing an infinite family of Type 1 nanodiscs.