Building a Maximal Independent Set for the Vertex-coloring Problem on Planar Graphs
Autor: | Guillermo De Ita Luna, Jorge Eduardo Gutiérrez Gómez, 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 GeneralLiterature_MISCELLANEOUS Graph Theoretical Computer Science Planar graph Vertex (geometry) Computer Science::Robotics Combinatorics symbols.namesake 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering symbols Maximal independent set Coloring problem ComputingMethodologies_COMPUTERGRAPHICS MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
Zdroj: | Electronic Notes in Theoretical Computer Science. 354:75-89 |
ISSN: | 1571-0661 |
Popis: | We analyze the vertex-coloring problem restricted to planar graphs and propose to consider classic wheels and polyhedral wheels as basic patterns for the planar graphs. We analyze the colorability of the composition among wheels and introduce a novel algorithm based on three rules for the vertex-coloring problem. These rules are: 1) Selecting vertices in the frontier. 2) Processing subsumed wheels. 3) Processing centers of the remaining wheels. Our method forms a maximal independent set S1 ⊂ V (G) consisting of wheel's centers, and a maximum number of vertices in the frontier of the planar graph. Thus, we show that if the resulting graph G′ = (G − S1) is 3-colorable, then this implies the existence of a valid 4-coloring for G. |
Databáze: | OpenAIRE |
Externí odkaz: |