Vertex coloring of a graph for memory constrained scenarios (Q2183733)

A (proper) \(k\)-\textit{vertex coloring} of an undirected graph \(G=(V, E)\) with colors \(C = \{c_1, \dots, c_k\}\) is a function \(\phi : V \to C\) for which \(\phi(a) \neq \phi(b)\) whenever \(\{a,b\} \in E\). A graph \(G\) is \(k\)-\textit{colorable} when it admits a \(k\)-vertex coloring. The \textit{chromatic number} of \(G\) is the smallest \(k\) for which \(G\) is \(k\)-colorable. When \(k \geq 3\), it is NP-complete to decide whether a graph is \(k\)-colorable. Because vertex coloring has numerous practical applications such as resource scheduling, compiler register allocation, pattern matching, puzzle solving, and exam timetabling, efficient algorithms to approximate the chromatic number have been developed. In this paper, a need is identified for approximation methods that are suitable for memory-constrained microprocessors with limited instruction sets, such as sensors. A heuristic vertex coloring method is proposed that uses simple operations and limited storage. Computational results are shown to illustrate the effectiveness of the proposed method.