ABSTRACT
Graph coloring is a prime element of graph theory, with various applications in different fields. Graph coloring is used in aircraft scheduling, Sudoku, mobile networking, register allocation, etc. This chapter describes the HB color matrix (HBCM) method for the perfect coloring of graphs. HBCM is a matrix with elements of 0’s and ∞’s. Cells in the matrix will have a value 0 if any element (vertex, edge, or region) of the graph is not adjacent to any other element of the graph, otherwise they will have the value ∞. Perfect coloring is the process of assigning colors to vertices, edges, and regions of the graph with certain constraints. The minimum number of colors required to color any graph using perfect coloring is the perfect chromatic (PC) number of the graph. The perfect HBCM algorithm defined in this chapter. calculates the PC number by making assignments in the HBCM. The algorithm is demonstrated for a house graph. A Python program developed using the methodology of the perfect HBCM algorithm and the output for few standard graphs is described.
