Coloração total e problema Firefighter em grafos cúbicos

Abstract

In this master’s thesis we tackle two problems in Graph Theory well inserted historical contexts, with open problems and with our results. We first study total coloring in graphs. A total coloring of a graph G is an assignment of colors to the edges and vertices of G so that adjacent and incident elements have different colors. Open for more than 50 years, we have the Total Coloring Conjecture as principal motivation, which limits the total chromatic number of G to its maximum degree plus two units. In this work we present the study we have developed on the total coloring of generalized Petersen graphs, classifying some infinite families of this class of graphs as Type1, exhibiting a Δ +1-total coloring for them. The main technique used to coloring them is the joining of blocks of these graphs developed y Sasaki, thus contemplating infinite graphs as we join these blocks. Another problem addressed in this work is the Firefighter problem, also approached as a combinatorial game, which consists of a scenario where a vertex is set on fire, and then, one or more vertices are chosen to be defended per step, preventing the fire from reaching these vertices or passing through them. In the subsequent steps, the fire spreads to adjacent vertices, and then another vertex to be defended is chosen. The main objectives of this problem are to defend a considerable number of vertices or to stop the fire from spreading as soon as possible. In this work, we present a lower and upper bound for the surviving rate, a parameter used to calculate the proportion of saved vertices in the graph, of three infinite families of fullerene graphs: the full icosahedral symmetry fullerene graphs Gi,0 and Gi,i and the fullerene nanodiscs Dr. Furthermore, for this approach, we propose a spiral planar representation for the full icosahedral symmetry fullerene graphs, based on the Spiral Conjecture. We also study this problem on the dual graphs of these fullerenes and on the two families of Loupekine’s snarks, LO¹k and LO²k. A part of the results in the Firefighter problem was achieved with computational assistance, and thus, we dedicate a section to present it.