EQUITABLE COLORING OF CORONA PRODUCTS OF GRAPHS
In many applications in sequencing and scheduling it is desirable to have an underlaying graph as equitably colored as possible. In this paper, we consider an equitable coloring of some corona products of two graphs G and H. In particular, we show that deciding the colorability of is NP-complete even if G is 4-regular and H is Next, we prove exact values or upper bounds on the equitable chromatic number where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph. Our proofs are constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that an equitable coloring of G is given. As a by-product we obtain a new class of graphs that confirm Equitable Coloring Conjecture.
corona graph, equitable chromatic number, equitable graph coloring, NP-completeness, polynomial algorithm.