Broadcast Chromatic Numbers of Graphs

Abstract

A function \(f: V \to \{1,\ldots,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) \leq 3\), we show that it is \(NP\)-hard to determine if \(\chi_b(G) \leq 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.