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

#### Abstract

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 *χ*_{ = }(*G*). In this paper the problem of determinig *χ*_{ = } 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 *χ*_{ = }(*G*) or *χ*_{ = }(*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.

#### Keywords

DOI: https://doi.org/10.26493/1855-3974.687.99b

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications