Geodesic
Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
Ars Mathematica Contemporanea, Tome 10 (2016) no. 2, pp. 333-347.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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.
DOI : 10.26493/1855-3974.687.99b
Keywords: Corona graph, cubic graph, equitable chromatic number, equitable graph coloring, NP-hardness, polynomial algorithm 
@article{10_26493_1855_3974_687_99b,
     author = {Hanna Furmanczyk and Marek Kubale},
     title = {Equitable coloring of corona products of cubic graphs is harder than ordinary coloring},
     journal = {Ars Mathematica Contemporanea},
     pages = {333--347},
     publisher = {mathdoc},
     volume = {10},
     number = {2},
     year = {2016},
     doi = {10.26493/1855-3974.687.99b},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.687.99b/}
}
TY  - JOUR
AU  - Hanna Furmanczyk
AU  - Marek Kubale
TI  - Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
JO  - Ars Mathematica Contemporanea
PY  - 2016
SP  - 333
EP  - 347
VL  - 10
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.687.99b/
DO  - 10.26493/1855-3974.687.99b
LA  - en
ID  - 10_26493_1855_3974_687_99b
ER  - 
%0 Journal Article
%A Hanna Furmanczyk
%A Marek Kubale
%T Equitable coloring of corona products of cubic graphs is harder than ordinary coloring
%J Ars Mathematica Contemporanea
%D 2016
%P 333-347
%V 10
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.687.99b/
%R 10.26493/1855-3974.687.99b
%G en
%F 10_26493_1855_3974_687_99b
Hanna Furmanczyk; Marek Kubale. Equitable coloring of corona products of cubic graphs is harder than ordinary coloring. Ars Mathematica Contemporanea, Tome 10 (2016) no. 2, pp. 333-347. doi : 10.26493/1855-3974.687.99b. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.687.99b/

Cité par Sources :