A Heuristic for the Coloring of Planar Graphs
| Autor: | Jorge E. Gutiérrez-Gómez, Ana E. De Ita-Varela, Guillermo De Ita Luna, Cristina López-Ramírez |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Theoretical Computer Science Planar graph Vertex (geometry) Combinatorics symbols.namesake Critical regions 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols Maximal independent set MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Electronic Notes in Theoretical Computer Science. 354:91-105 |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2020.10.008 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect