On the Irreducible No-hole $L(2,1)$ Coloring of Bipartite Graphs and Cartesian Products

Abstract

The channel assignment problem is the problem of assigning radio frequencies to transmitters while avoiding interference. This problem can be modeled and examined using graphs and graph colorings. $L(2,1)$ coloring was first studied by Griggs and Yeh [6] as a model of a variation of the channel assignment problem. A no-hole coloring, introduced in [4], is defined to be an $L(2,1)$ coloring of a graph which uses all the colors $\{0,1,\dots ,k\}$ for some integer $k$. An $L(2,1)$ coloring is irreducible, introduced in [3], if no vertex labels in the graph can be decreased and yield another $L(2,1)$ coloring. A graph $G$ is inh-colorable if there exists an irreducible no-hole coloring on $G$.

We consider the inh-colorability of bipartite graphs and Cartesian products. We obtain some sufficient conditions for bipartite graphs to be inh-colorable. We also find the optimal inh-coloring for some Cartesian products, including grid graphs and the rook’s graph.