A Heuristic for the Coloring of Planar Graphs
Guillermo De Ita Luna, Cristina López-Ramírez, Ana E. De Ita-Varela, Jorge Eduardo Gutiérrez Gómez · Electronic Notes in Theoretical Computer Science · 2020
We present an algorithm for the coloring of planar graphs based on the construction of a maximal independent set S of the input graph. The maximal independent set S must fulfill certain characteristics. For example, S contains the vertex that appears in a maximum number of odd cycles of G. The construction of S considers the internal-face graph of the input graph G in order to select each vertex belonging to a maximal number of odd faces of G. The traversing in pre-order on the internal-face graph Gf of the input planar graph G provides us of a strategy for the construction of partial maximal independent sets of critical regions of Gf. Thus, the union of these partial maximal independent sets forms a maximal independent set S of G. This allows us to color first the vertices that are crucial for decomposing G in a graph (G − S), which is a polygonal tree, and therefore, is 3-colorable.