Packing coloring

In graph theory, a packing coloring (also called a broadcast coloring) is a type of graph coloring where vertices are assigned colors (represented by positive integers) such that the distance between any two vertices with the same color is greater than . The packing chromatic number (or broadcast chromatic number) (or ) of a graph is the minimum number of colors needed for a packing coloring.

Definition

A packing coloring of a graph is a function such that if , then the distance . The minimum for which such a coloring exists is the packing chromatic number .

Equivalently, a packing coloring is a partition of the vertex set where each is an -packing (vertices at pairwise distance more than ).

Basic properties

For any graph with vertices:

, where is the clique number and is the chromatic number
, where is the vertex cover number, with equality if and only if has diameter two
, where is the independence number
If , then

Complexity

Determining whether can be solved in polynomial time, while determining whether is NP-hard, even for planar graphs.

The problem remains NP-hard for diameter 2 graphs, since computing the vertex cover number is NP-hard for such graphs.

The problem is NP-complete for trees, resolving a long-standing open question. However, it can be solved in polynomial time for graphs of bounded treewidth and bounded diameter.

Specific graph families

For path graphs :

for
for

For cycle graphs with :

if is or a multiple of
otherwise

For trees of order :

for all trees except and two specific -vertex trees
The star graph has
Trees of diameter have
The bound is sharp and achieved by specific tree constructions

For the hypercube graph

asymptotically
With ...:

:...

For complete graphs :

for

For bipartite graphs of diameter :

For complete multipartite graphs and wheel graphs :

For the grid graph :

for
for
for
for
for any finite grid
For ... (the square grid graphs):

:...

The infinite square grid has:

The infinite hexagonal lattice has:

The infinite triangular lattice has infinite packing chromatic number.

For the subdivision graph of a graph , obtained by subdividing every edge once:

For connected graphs with at least 3 vertices:

:

For connected bipartite graphs with at least two edges:

:

Graph products

For Cartesian products of connected graphs and with at least two vertices:

For the Cartesian product with complete graphs:

Characterizations

A connected graph has if and only if is a star.

A graph has if and only if it can be formed by taking a bipartite multigraph, subdividing every edge exactly once, adding leaves to some vertices, and performing a single -add operation to some vertices.

Applications

Packing colorings model frequency assignment problems in broadcasting, where radio stations must be assigned frequencies such that stations with the same frequency are sufficiently far apart to avoid interference. The distance requirement increases with the power of the broadcast signal.

Related concepts

Dominating broadcast: A function where (eccentricity) and every vertex with has a neighbor with and
Broadcast independence: A broadcast where implies
-packing coloring (or -coloring): For a non-decreasing sequence of positive integers, vertices in color class must be at distance greater than apart. The standard packing coloring corresponds to . The -packing chromatic number is the minimum number of colors needed.

References