Given an undirected graph $$G=(V,E)$$ G = ( V , E ) , where V is a set of n vertices and E is a set of m edges, the… Click to show full abstract
Given an undirected graph $$G=(V,E)$$ G = ( V , E ) , where V is a set of n vertices and E is a set of m edges, the vertex coloring problem consists in assigning colors to the graph vertices such that no two adjacent vertices share the same color. The vertex coloring problem has several practical applications, for instance, resource scheduling, compiler register allocation, pattern matching, puzzle solving, exam timetabling, among others. It is known that the problem of vertex k -coloring of a graph, for any $$k \ge 3$$ k ≥ 3 , is NP-complete. In this work, we focus on an approximate solution that can be implemented on simple electronic equipments that do not require a complete set of operations present in common microprocessors. The solution is suitable for sensors and other devices present in several applications for collecting and measuring data.
               
Click one of the above tabs to view related content.