Limited packings: Related vertex partitions and duality issues.

A k -limited packing partition (k LP partition) of a graph G is a partition of V (G) into k -limited packing sets. We consider the k LP partitions with minimum cardinality (with emphasis on k = 2). The minimum cardinality is called k LP partition number of G and denoted by χ × k (G). This problem is the dual problem of k -tuple domatic partitioning as well as a generalization of the well-studied 2-distance coloring problem in graphs. We give the exact value of χ × 2 for trees and bound it for general graphs. A section of this paper is devoted to the dual of this problem, where we give a solution to an open problem posed in 1998. We also revisit the total limited packing number in this paper and prove that the problem of computing this parameter is NP-hard even for some special families of graphs. We give some inequalities concerning this parameter and discuss the difference between 2TLP number and 2LP number with emphasis on trees. [ABSTRACT FROM AUTHOR]