The Packing Coloring Problem for (q,q-4) graphs

G. R. ARGIROFFO; G. NASINI; P. D. TORRES

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2012 vol. 7422 p. 309 - 319

0302-9743

It is known that computing the packing chromatic number of a graph is an NP-hard problem, even when restricted to tree graphs. This fact naturally leads to the search of graph families where this problem is polynomial time solvable.Babel et al. (2001) showed that a large variety of NP-complete problems can be efficiently solved for the class of $(q,q-4)$ graphs, for every fixed $q$. In this work we show that also to compute the packing chromatic number can be efficiently solved for the class of $(q,q-4)$ graphs.