INVESTIGADORES
TORRES Pablo Daniel
artículos
Título:
The packing coloring problem for lobsters and partner limited graphs
Autor/es:
G. R. ARGIROFFO; G. NASINI; P. D. TORRES
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2014 vol. 164 p. 373 - 382
ISSN:
0166-218X
Resumen:
A emph{packing $k$-coloring} of a graph $G$ is a $k$-coloring such that the distance between two vertices having color $i$ is at least $i+1$. To compute the emph{packing chromatic number} is NP-hard, even restricted to trees and it is known to be polynomial time solvable only for a few graph classes, including cographs and split graphs. In this work, we provide upper bounds for the packing chromatic number of lobsters and we prove that it can be computed in polynomial time for an infinite subclass of them, including caterpillars. In addition, we provide superclasses of split graphs where the packing chromatic number can be computed in polynomial time. Moreover, we prove that the packing chromatic number can be computed in polynomial time for the class of partner limited graphs, a superclass of cographs, including also $P_4$-sparce and $P_4$-tidy graphs.