Equitable coloring of corona products of cubic graphs is harder than ordinary coloring

english

2016

volume 10, issue 2

corona graph   cubic graph   equitable chromatic number   equitable graph coloring   NP-hardness   polynomial algorithm

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

A graph is equitably $k$-colorable if its vertices can be partitioned into ?$k$? independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest ?$k$? for which such a coloring exists is known as the equitable chromatic number of ?$G$? and it is denoted by ?$\chi_=(G)$?. In this paper the problem of determinig ?$\chi_ =$? for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses ?$\chi_=(G)$? or ?$\chi_=(G)+1$? colors. Our algorithm is best possible, unless P=NP. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloring.

29.05.2020