Department of
Applied
Mathematics

On packing coloring for trees and grids

Jiøí Fiala

Abstract

Based on joint works with P. Golovach, B. Lidicky and S. Klavzar.

Packing coloring is a partition of the vertex set of a (possibly infinite) graph into classes X_1,X_2,... such that each class X_k is a k-packing - i.e. distances between vertices in X_k are greater than k. Note that some classes in the partition may be empty. In the case when G is infinite, the number of nonempty classes may be infinite as well.

We review some bounds on the number of color classes necessary to color trees or grids and also address some computational issues.