ABSTRACT
A proper coloring of a graph G = (V, E) is an assignment of colors to all vertices in V in such a way that no two adjacent vertices have the same color. A k-coloring of G is a coloring that uses k colors. The minimum number of colors that can be used to properly color G is the (vertex) chromatic number of G and is denoted by χ (G). Finding the chromatic number of a graph is a fundamental problem in computer science, with various applications related to collision avoidance and message inhibition methods [1], range assignment problems in directional antennas’ optimization [2], coordination aspects of MAC access in sensor networks [3], and more.
