# Packing coloring

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Packing_coloring
> Markdown URL: https://mediated.wiki/source/Packing_coloring.md
> Source: https://en.wikipedia.org/wiki/Packing_coloring
> Source revision: 1327511270
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Graph coloring variant in graph theory}}
In [graph theory](/source/graph_theory), a '''packing coloring''' (also called a '''broadcast coloring''') is a type of [graph coloring](/source/graph_coloring) where vertices are assigned colors (represented by positive integers) such that the distance between any two vertices with the same color <math>i</math> is greater than <math>i</math>. The '''packing chromatic number''' (or '''broadcast chromatic number''') <math>\chi_\rho(G)</math> (or <math>\chi_b(G)</math>) of a graph <math>G</math> is the minimum number of colors needed for a packing coloring.<ref name="Goddard2008">{{cite journal |last1=Goddard |first1=Wayne |last2=Hedetniemi |first2=Sandra M. |last3=Hedetniemi |first3=Stephen T. |last4=Harris |first4=John M. |last5=Rall |first5=Douglas F. |title=Broadcast Chromatic Numbers of Graphs |journal=Ars Combinatoria |volume=86 |year=2008 |pages=33–49 |url=https://combinatorialpress.com/ars-articles/volume-086-ars-articles/broadcast-chromatic-numbers-of-graphs/}}</ref>

== Definition ==
A '''packing coloring''' of a graph <math>G = (V,E)</math> is a function <math>\pi : V \to \{1,2,\ldots,k\}</math> such that if <math>\pi(u) = \pi(v)</math>, then the distance <math>d(u,v) > \pi(u)</math>. The minimum <math>k</math> for which such a coloring exists is the '''packing chromatic number''' <math>\chi_\rho(G)</math>.<ref name="Goddard2008"/>

Equivalently, a packing coloring is a partition <math>\mathcal{P}_\pi = \{V_1, V_2, \ldots, V_k\}</math> of the vertex set where each <math>V_i</math> is an <math>i</math>-packing (vertices at pairwise distance more than <math>i</math>).<ref name="Goddard2008"/>

== Basic properties ==
For any graph <math>G</math> with <math>n</math> vertices:
* <math>\omega(G) \leq \chi(G) \leq \chi_\rho(G)</math>, where <math>\omega(G)</math> is the [clique number](/source/clique_number) and <math>\chi(G)</math> is the [chromatic number](/source/chromatic_number)<ref name="Goddard2008"/>
* <math>\chi_\rho(G) \leq \alpha_0(G) + 1</math>, where <math>\alpha_0(G)</math> is the [vertex cover](/source/vertex_cover) number, with equality if and only if <math>G</math> has diameter two<ref name="Goddard2008"/>
* <math>\chi_\rho(G) \leq n - \alpha(G) + 1</math>, where <math>\alpha(G)</math> is the [independence number](/source/independence_number)<ref name="Survey2020">{{cite journal |last1=Brešar |first1=Boštjan |last2=Ferme |first2=Jasmina |last3=Klavžar |first3=Sandi |last4=Rall |first4=Douglas F. |title=A survey on packing colorings |journal=Discussiones Mathematicae Graph Theory |volume=40 |year=2020 |pages=923–970 |doi=10.7151/dmgt.2320 |url=https://users.fmf.uni-lj.si/klavzar/preprints/DMGT-2320.pdf}}</ref>
* If <math>\chi_\rho(G) = \chi(G)</math>, then <math>\omega(G) = \chi(G)</math><ref name="Survey2020"/>

== Complexity ==
Determining whether <math>\chi_\rho(G) \leq 3</math> can be solved in polynomial time, while determining whether <math>\chi_\rho(G) \leq 4</math> is [NP-hard](/source/NP-hard), even for [planar graph](/source/planar_graph)s.<ref name="Goddard2008"/>

The problem remains NP-hard for [diameter](/source/diameter_(graph_theory)) 2 graphs, since computing the vertex cover number is NP-hard for such graphs.<ref name="Goddard2008"/>

The problem is NP-complete for trees,<ref name="Survey2020"/> resolving a long-standing open question. However, it can be solved in polynomial time for graphs of bounded [treewidth](/source/treewidth) and bounded diameter.<ref name="Survey2020"/>

== Specific graph families ==

For [path graph](/source/path_graph)s <math>P_n</math>:
* <math>\chi_\rho(P_n) = 2</math> for <math>2 \leq n \leq 3</math>
* <math>\chi_\rho(P_n) = 3</math> for <math>n \geq 4</math>

For [cycle graph](/source/cycle_graph)s <math>C_n</math> with <math>n \geq 3</math>:
* <math>\chi_\rho(C_n) = 3</math> if <math>n</math> is <math>3</math> or a multiple of <math>4</math>
* <math>\chi_\rho(C_n) = 4</math> otherwise

For [trees](/source/tree_(graph_theory)) <math>T</math> of order <math>n</math>:<ref name="Goddard2008"/>
* <math>\chi_\rho(T) \leq (n+7)/4</math> for all trees except <math>P_4</math> and two specific <math>8</math>-vertex trees
* The [star graph](/source/star_graph) <math>K_{1,n-1}</math> has <math>\chi_\rho(K_{1,n-1}) = 2</math>
* Trees of [diameter](/source/diameter_(graph_theory)) <math>3</math> have <math>\chi_\rho(T) = 3</math>
* The bound <math>(n+7)/4</math> is sharp and achieved by specific tree constructions

For the [hypercube graph](/source/hypercube_graph) <math>Q_k</math><ref name="Goddard2008"/><ref>{{cite journal |last1=Torres |first1=Pablo |last2=Valencia-Pabon |first2=Mario |year=2015 |title=The packing chromatic number of hypercubes |journal=Discrete Applied Mathematics |volume=190–191 |pages=127–140 |doi=10.1016/j.dam.2015.04.006 |issn=0166-218X |url=https://hal.science/hal-00926875}}</ref>
* <math>\chi_\rho(Q_k) \sim \frac{1}{2} \cdot O(1/k) \cdot 2^k</math> asymptotically
* With <math>k = 1, 2, 3, 4</math>...:
::<math>\chi_\rho(Q_k) = 2, 3, 5, 7, 15, 25, 49, 95</math>... {{OEIS|id=A335203}}

For [complete graph](/source/complete_graph)s <math>K_n</math>: 
* <math>\chi_\rho(K_n) = n</math>
* <math>\chi_\rho(S(K_n)) = n + 1</math> for <math>n \geq 3</math>

For [bipartite graph](/source/bipartite_graph)s <math>G</math> of diameter <math>3</math>:
:<math>\alpha_0(G) \leq \chi_\rho(G) \leq \alpha_0(G) + 1</math>

For [complete multipartite graph](/source/complete_multipartite_graph)s and [wheel graph](/source/wheel_graph)s <math>G</math>:
:<math>\chi_\rho(G) = \alpha_0(G) + 1</math>

For the <math>r \times c</math> [grid graph](/source/grid_graph) <math>G_{r,c}</math>:<ref name="Goddard2008"/><ref name="Subercaseaux2023">{{cite conference |last1=Subercaseaux |first1=B. |last2=Heule |first2=M.J.H. |year=2023 |title=The Packing Chromatic Number of the Infinite Square Grid is 15 |book-title=Tools and Algorithms for the Construction and Analysis of Systems |series=Lecture Notes in Computer Science |volume=13993 |publisher=Springer, Cham |doi=10.1007/978-3-031-30823-9_20 |arxiv=2301.09757 |editor1-last=Sankaranarayanan |editor1-first=S. |editor2-last=Sharygina |editor2-first=N.}}</ref>
* <math>\chi_\rho(G_{2,c}) = 5</math> for <math>c \geq 6</math>
* <math>\chi_\rho(G_{3,c}) = 7</math> for <math>c \geq 12</math>
* <math>\chi_\rho(G_{4,c}) = 8</math> for <math>c \geq 10</math>
* <math>\chi_\rho(G_{5,c}) = 9</math> for <math>c \geq 10</math>
* <math>\chi_\rho(G_{r,c}) \leq 23</math> for any finite grid
* For <math>r = c = 1, 2, 3, 4</math>... (the [square grid graph](/source/square_lattice)s):
::<math>\chi_\rho(G_{r,c}) = 1, 3, 4, 5, 7, 8, 9, 9, 10, 11</math>... {{OEIS|id=A362580}}

The infinite [square grid](/source/square_lattice) <math>G_{\infty,\infty}</math> has:<ref name="Subercaseaux2023"/>
:<math>\chi_\rho(G_{\infty,\infty}) = 15</math>

The infinite [hexagonal lattice](/source/hexagonal_lattice) <math>H</math> has:<ref name="Survey2020"/>
:<math>\chi_\rho(H) = 7</math>

The infinite [triangular lattice](/source/triangular_lattice) has infinite packing chromatic number.<ref name="Survey2020"/>

For the [subdivision graph](/source/subdivision_graph) <math>S(G)</math> of a graph <math>G</math>, obtained by subdividing every edge once:<ref name="Bresar2007"/>
*For [connected graph](/source/connected_graph)s <math>G</math> with at least 3 vertices:
::<math>\omega(G) + 1 \leq \chi_\rho(S(G)) \leq \chi_\rho(G) + 1</math>
*For connected bipartite graphs with at least two edges:
::<math>\chi_\rho(S(G)) = 3</math>

=== Graph products ===
For [Cartesian products](/source/Cartesian_product_of_graphs) <math>G \square H</math> of connected graphs <math>G</math> and <math>H</math> with at least two vertices:<ref name="Bresar2007">{{cite journal |last1=Brešar |first1=Boštjan |last2=Klavžar |first2=Sandi |last3=Rall |first3=Douglas F. |title=On the packing chromatic number of Cartesian products, hexagonal lattice, and trees |journal=Discrete Applied Mathematics |volume=155 |issue=17 |year=2007 |pages=2303–2311 |doi=10.1016/j.dam.2007.06.008 |url=https://users.fmf.uni-lj.si/klavzar/preprints/packing-2007-scan.pdf}}</ref>

:<math>\chi_\rho(G \square H) \geq (\chi_\rho(G) + 1)|H| - \text{diam}(G \square H)(|H| - 1) - 1</math>

For the Cartesian product with complete graphs:<ref name="Bresar2007"/>
:<math>\chi_\rho(G \square K_n) \geq n\chi_\rho(G) - (n-1)\text{diam}(G)</math>

== Characterizations ==

A connected graph <math>G</math> has <math>\chi_\rho(G) = 2</math> if and only if <math>G</math> is a star.

A graph has <math>\chi_\rho(G) = 3</math> 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 <math>T</math>-add operation to some vertices.<ref name="Goddard2008"/>

== 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.<ref name="Goddard2008"/>

== Related concepts ==
* '''Dominating broadcast''': A function <math>b : V \to \{0,1,\ldots\}</math> where <math>b(u) \leq e(u)</math> (eccentricity) and every vertex with <math>b(v) = 0</math> has a neighbor <math>u</math> with <math>b(u) > 0</math> and <math>d(u,v) \leq b(u)</math>
* '''Broadcast independence''': A broadcast where <math>b(u), b(v) > 0</math> implies <math>d(u,v) > b(u)</math>
* '''<math>S</math>-packing coloring''' (or '''<math>(s_1,s_2,\ldots,s_k)</math>-coloring'''): For a non-decreasing sequence <math>S = (s_1, s_2, \ldots)</math> of positive integers, vertices in color class <math>i</math> must be at distance greater than <math>s_i</math> apart. The standard packing coloring corresponds to <math>S = (1, 2, 3, \ldots)</math>. The <math>S</math>-packing chromatic number <math>\chi_S(G)</math> is the minimum number of colors needed.<ref name="Goddard2008"/><ref name="Survey2020"/>

== See also ==
* [Graph coloring](/source/Graph_coloring)
* [List coloring](/source/List_coloring)
* [Fractional coloring](/source/Fractional_coloring)
* [Acyclic coloring](/source/Acyclic_coloring)

== References ==
{{reflist}}

Category:Graph coloring
Category:NP-complete problems

---
Adapted from the Wikipedia article [Packing coloring](https://en.wikipedia.org/wiki/Packing_coloring) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Packing_coloring?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.