Advances and Applications in Discrete Mathematics
Volume 11, Issue 2, Pages 103 - 120
(April 2013)
|
|
EQUITABLE COLORING OF CORONA PRODUCTS OF GRAPHS
Hanna Furmańczyk, K. Kaliraj, Marek Kubale and J. Vernold Vivin
|
Abstract: 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. |
Keywords and phrases: corona graph, equitable chromatic number, equitable graph coloring, NP-completeness, polynomial algorithm. |
|
Number of Downloads: 256 | Number of Views: 766 |
|