Broadcast Chromatic Numbers of Graphs

Abstract

A function $f:V\to \{1,\dots ,k\}$ is a broadcast coloring of order $k$ if $\pi (u)=\pi (v)$ implies that the distance between $u$ and $v$ is more than $\pi (u)$. The minimum order of a broadcast coloring is called the broadcast chromatic number of $G$, and is denoted ${\chi }_b(G)$. In this paper we introduce this coloring and study its properties. In particular, we explore the relationship with the vertex cover and chromatic numbers. While there is a polynomial-time algorithm to determine whether ${\chi }_b(G)\le 3$, we show that it is $NP$-hard to determine if ${\chi }_b(G)\le 4$. We also determine the maximum broadcast chromatic number of a tree, and show that the broadcast chromatic number of the infinite grid is finite.