Coloração total em grafos grades parciais

Abstract

A total coloring of a graph is an assignment of colors to its vertices and edges in such a way that any two adjacent vertices have distinct colors, any two edges sharing a vertex have distinct colors, and any vertex has a color different from the colors of the edges incident to it.The Total Coloring Problem is, given a graph 𝐺, to determine the minimum number of colors that allows a total coloring of 𝐺. This number is called the total chromatic number of 𝐺. Given a graph 𝐺 and an integer 𝑘, deciding whether 𝐺 has a total coloring with 𝑘 colors is an NP-complete problem, even when restricted to bipartite graphs. A subclass of bipartite graphs is partial grids. For partial grids, the total chromatic number is known unless the maximum degree of the graph is equal to 3. In this case, there are some partial results.In this work, we reduce the problem of determining the chromatic number of partial grids with a maximum degree of 3 to the problem of determining the chromatic number of biconnected partial grids with a maximum degree of 3, which have chords and whose subgraphs induced by vertices of degree 2 are paths with at most 2 vertices.