A cubic graph is Type 1 if it has a total coloring with 4 colors, and Type 2 otherwise; in this case, it is known that it has a total coloring with 5 colors. A total coloring is equitable if the cardinalities of any two color classes differ by at most 1. Similarly, it is known that every cubic graph has an equitable total coloring with at most 5 colors.
The study of total coloring of cubic graphs considered in this thesis was motivated by the rich existing literature, especially by the question proposed by Cavicchioli et al. in 2003 of finding, if one exists, the smallest snark (a cubic, non 3-edge-colorable graph with additional connectivity properties) of girth at least 5 that is Type 2. In general, the main goal of this thesis is to confirm the difficulty of this question, through theoretical and computational results suggesting positive and negative answers to the question of whether such a graph exists, and through the formulation of two other related questions. These two new questions concern the non-4-total-colorability of cubic graphs with girth at least 5, one considering the total coloring and the other considering the equitable total coloring.
We contribute to the three questions above, exhibiting families of cubic graphs that indicate that the questions may have a negative answer. On the other hand, we present families of cubic graphs that are not 4-total-colorable, suggesting that the questions may have a positive answer. Moreover, we prove that the problem of determining if a cubic bipartite graph has an equitable 4-total-coloring is NP-complete and we analyze general properties of total coloring, including characterizations of Type 1 cubic graphs and some relevant examples.