Optimal coloring of a plane using unit distance graphs

Abstract

Generally, plane coloring is the assignment of different colors to different points of a plane. Plane can be represented via graphs and hence can be colored using graph coloring. So the chromatic number of a plane is equivalent to finding the chromatic number of the equivalent graph of the plane. The unit distance graph can be used to find the chromatic number of a plane. The main application of unit distance graphs is the unit distance wireless networks (UDW), in cellular networks; the geometric regions are partitioned into hexagonal cells. Unit distance graph can represent the hexagonal cells, and coloring the hexagonal regions implies distribution of frequencies among the hexagonal cells. Different heuristic based algorithms viz. contraction based RLF, DSATUR and IDO based graph coloring algorithms are used in this study in order to color the unit distance graphs. And, different simple unit distance graphs used during the study include wheel graph, cycle graph, grid graph, etc. as test cases for these coloring algorithms.

The optimality of plane coloring, nowadays, is no more just confined to the minimal number of colors rather the coloring time makes importance. Since, coloring time is important in the field of cellular networks as the assignments of the frequency in a geometric regions and assignment of data to registers in program execution in minimum time. Since, these problems can be resolved through graph coloring. In this context, this study analyzes on optimal coloring of planes using heuristic based approaches so as to suggest an effective coloring paradigm.