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 ${\displaystyle i}$ is greater than ${\displaystyle i}$. The packing chromatic number (or broadcast chromatic number) ${\displaystyle \chi _{\rho }(G)}$ (or ${\displaystyle \chi _{b}(G)}$) of a graph ${\displaystyle G}$ is the minimum number of colors needed for a packing coloring. ^[1]

Definition

A packing coloring of a graph ${\displaystyle G=(V,E)}$ is a function ${\displaystyle \pi :V\to \{1,2,\ldots ,k\}}$ such that if ${\displaystyle \pi (u)=\pi (v)}$, then the distance ${\displaystyle d(u,v)>\pi (u)}$. The minimum ${\displaystyle k}$ for which such a coloring exists is the packing chromatic number${\displaystyle \chi _{\rho }(G)}$. ^[1]

Equivalently, a packing coloring is a partition ${\displaystyle {\mathcal {P}}_{\pi }=\{V_{1},V_{2},\ldots ,V_{k}\}}$ of the vertex set where each ${\displaystyle V_{i}}$ is an ${\displaystyle i}$-packing (vertices at pairwise distance more than ${\displaystyle i}$). ^[1]

Basic properties

For any graph ${\displaystyle G}$ with ${\displaystyle n}$ vertices:

• ${\displaystyle \omega (G)\leq \chi (G)\leq \chi _{\rho }(G)}$, where ${\displaystyle \omega (G)}$ is the clique number and ${\displaystyle \chi (G)}$ is the chromatic number ^[1]
• ${\displaystyle \chi _{\rho }(G)\leq \alpha _{0}(G)+1}$, where ${\displaystyle \alpha _{0}(G)}$ is the vertex cover number, with equality if and only if ${\displaystyle G}$ has diameter two ^[1]
• ${\displaystyle \chi _{\rho }(G)\leq n-\alpha (G)+1}$, where ${\displaystyle \alpha (G)}$ is the independence number ^[2]
• If ${\displaystyle \chi _{\rho }(G)=\chi (G)}$, then ${\displaystyle \omega (G)=\chi (G)}$ ^[2]

Complexity

Determining whether ${\displaystyle \chi _{\rho }(G)\leq 3}$ can be solved in polynomial time, while determining whether ${\displaystyle \chi _{\rho }(G)\leq 4}$ is NP-hard, even for planar graphs. ^[1]

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

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

Specific graph families

For path graphs ${\displaystyle P_{n}}$:

• ${\displaystyle \chi _{\rho }(P_{n})=2}$ for ${\displaystyle 2\leq n\leq 3}$
• ${\displaystyle \chi _{\rho }(P_{n})=3}$ for ${\displaystyle n\geq 4}$

For cycle graphs ${\displaystyle C_{n}}$ with ${\displaystyle n\geq 3}$:

• ${\displaystyle \chi _{\rho }(C_{n})=3}$ if ${\displaystyle n}$ is ${\displaystyle 3}$ or a multiple of ${\displaystyle 4}$
• ${\displaystyle \chi _{\rho }(C_{n})=4}$ otherwise

For trees ${\displaystyle T}$ of order ${\displaystyle n}$: ^[1]

• ${\displaystyle \chi _{\rho }(T)\leq (n+7)/4}$ for all trees except ${\displaystyle P_{4}}$ and two specific ${\displaystyle 8}$-vertex trees
• The star graph ${\displaystyle K_{1,n-1}}$ has ${\displaystyle \chi _{\rho }(K_{1,n-1})=2}$
• Trees of diameter ${\displaystyle 3}$ have ${\displaystyle \chi _{\rho }(T)=3}$
• The bound ${\displaystyle (n+7)/4}$ is sharp and achieved by specific tree constructions

For the hypercube graph ${\displaystyle Q_{k}}$ ^{[1] [3]}

• ${\displaystyle \chi _{\rho }(Q_{k})\sim {\frac {1}{2}}\cdot O(1/k)\cdot 2^{k}}$ asymptotically
• With ${\displaystyle k=1,2,3,4}$...:

${\displaystyle \chi _{\rho }(Q_{k})=2,3,5,7,15,25,49,95}$... (sequence A335203 in the OEIS )

For complete graphs ${\displaystyle K_{n}}$:

• ${\displaystyle \chi _{\rho }(K_{n})=n}$
• ${\displaystyle \chi _{\rho }(S(K_{n}))=n+1}$ for ${\displaystyle n\geq 3}$

For bipartite graphs ${\displaystyle G}$ of diameter ${\displaystyle 3}$:

${\displaystyle \alpha _{0}(G)\leq \chi _{\rho }(G)\leq \alpha _{0}(G)+1}$

For complete multipartite graphs and wheel graphs ${\displaystyle G}$:

${\displaystyle \chi _{\rho }(G)=\alpha _{0}(G)+1}$

For the ${\displaystyle r\times c}$ grid graph ${\displaystyle G_{r,c}}$: ^{[1] [4]}

• ${\displaystyle \chi _{\rho }(G_{2,c})=5}$ for ${\displaystyle c\geq 6}$
• ${\displaystyle \chi _{\rho }(G_{3,c})=7}$ for ${\displaystyle c\geq 12}$
• ${\displaystyle \chi _{\rho }(G_{4,c})=8}$ for ${\displaystyle c\geq 10}$
• ${\displaystyle \chi _{\rho }(G_{5,c})=9}$ for ${\displaystyle c\geq 10}$
• ${\displaystyle \chi _{\rho }(G_{r,c})\leq 23}$ for any finite grid
• For ${\displaystyle r=c=1,2,3,4}$... (the square grid graphs):

${\displaystyle \chi _{\rho }(G_{r,c})=1,3,4,5,7,8,9,9,10,11}$... (sequence A362580 in the OEIS )

The infinite square grid ${\displaystyle G_{\infty ,\infty }}$ has: ^[4]

${\displaystyle \chi _{\rho }(G_{\infty ,\infty })=15}$

The infinite hexagonal lattice ${\displaystyle H}$ has: ^[2]

${\displaystyle \chi _{\rho }(H)=7}$

The infinite triangular lattice has infinite packing chromatic number. ^[2]

For the subdivision graph ${\displaystyle S(G)}$ of a graph ${\displaystyle G}$, obtained by subdividing every edge once: ^[5]

• For connected graphs ${\displaystyle G}$ with at least 3 vertices:

${\displaystyle \omega (G)+1\leq \chi _{\rho }(S(G))\leq \chi _{\rho }(G)+1}$

• For connected bipartite graphs with at least two edges:

${\displaystyle \chi _{\rho }(S(G))=3}$

Graph products

For Cartesian products ${\displaystyle G\square H}$ of connected graphs ${\displaystyle G}$ and ${\displaystyle H}$ with at least two vertices: ^[5]

${\displaystyle \chi _{\rho }(G\square H)\geq (\chi _{\rho }(G)+1)|H|-{\text{diam}}(G\square H)(|H|-1)-1}$

For the Cartesian product with complete graphs: ^[5]

${\displaystyle \chi _{\rho }(G\square K_{n})\geq n\chi _{\rho }(G)-(n-1){\text{diam}}(G)}$

Characterizations

A connected graph ${\displaystyle G}$ has ${\displaystyle \chi _{\rho }(G)=2}$ if and only if ${\displaystyle G}$ is a star.

A graph has ${\displaystyle \chi _{\rho }(G)=3}$ 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 ${\displaystyle T}$-add operation to some vertices. ^[1]

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. ^[1]

Related concepts

• Dominating broadcast: A function ${\displaystyle b:V\to \{0,1,\ldots \}}$ where ${\displaystyle b(u)\leq e(u)}$ (eccentricity) and every vertex with ${\displaystyle b(v)=0}$ has a neighbor ${\displaystyle u}$ with ${\displaystyle b(u)>0}$ and ${\displaystyle d(u,v)\leq b(u)}$
• Broadcast independence: A broadcast where ${\displaystyle b(u),b(v)>0}$ implies ${\displaystyle d(u,v)>b(u)}$
• ${\displaystyle S}$-packing coloring (or ${\displaystyle (s_{1},s_{2},\ldots ,s_{k})}$-coloring): For a non-decreasing sequence ${\displaystyle S=(s_{1},s_{2},\ldots )}$ of positive integers, vertices in color class ${\displaystyle i}$ must be at distance greater than ${\displaystyle s_{i}}$ apart. The standard packing coloring corresponds to ${\displaystyle S=(1,2,3,\ldots )}$. The ${\displaystyle S}$-packing chromatic number ${\displaystyle \chi _{S}(G)}$ is the minimum number of colors needed. ^{[1] [2]}

See also

• Graph coloring
• List coloring
• Fractional coloring
• Acyclic coloring

References

1. Goddard, Wayne; Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; Harris, John M.; Rall, Douglas F. (2008). "Broadcast Chromatic Numbers of Graphs". Ars Combinatoria. 86: 33–49.
2. Brešar, Boštjan; Ferme, Jasmina; Klavžar, Sandi; Rall, Douglas F. (2020). "A survey on packing colorings" (PDF). Discussiones Mathematicae Graph Theory. 40: 923–970. doi:10.7151/dmgt.2320.
3. Torres, Pablo; Valencia-Pabon, Mario (2015). "The packing chromatic number of hypercubes". Discrete Applied Mathematics. 190–191: 127–140. doi:10.1016/j.dam.2015.04.006. ISSN   0166-218X.
4. Subercaseaux, B.; Heule, M.J.H. (2023). "The Packing Chromatic Number of the Infinite Square Grid is 15". In Sankaranarayanan, S.; Sharygina, N. (eds.). Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Vol. 13993. Springer, Cham. arXiv: 2301.09757 . doi:10.1007/978-3-031-30823-9_20.
5. Brešar, Boštjan; Klavžar, Sandi; Rall, Douglas F. (2007). "On the packing chromatic number of Cartesian products, hexagonal lattice, and trees" (PDF). Discrete Applied Mathematics. 155 (17): 2303–2311. doi:10.1016/j.dam.2007.06.008.