Channel assignment and multicolouring of the induced subgraphs of the triangular lattice (Q5936032)

Motivated by a real-world problem in mobile telecommunication, the main issue of the paper is a graph multicolouring problem. Let \(G\) be a finite triangle-free induced subgraph of the planar triangular grid and \(k\) be a natural number. We want to \(k\)-multicolour \(G\), that is to assign a set of \(k\) colours to each vertex of \(G\) so that adjacent vertices receive disjoint colour-sets. This task resembles the channel assignment problem for transmitters in a mobile telephone network. NEWLINENEWLINENEWLINEThe \([k]\)-chromatic number \(\chi_k(G)\) of a graph \(G\) is the least natural number \(n\) so that there is a \(k\)-multicolouring of \(G\) using colours only from \(\{1,2,\dots,n\}\). McDiarmid and Reed conjectured that for any triangle-free induced subgraph \(G\) of the planar triangular lattice we have \(\chi_k(G)\leq\lceil\frac{9k}{4}\rceil\) [see \textit{C. McDiarmid} and \textit{B. Reed}, Networks 36, No. 2, 114-117 (2000; Zbl 0971.90100)]. To prove the conjecture, it would suffice to prove that any such graph can be \(4\)-multicoloured with only \(9\) colours. The author proves two weaker statements: any such graph can be \(2\)-multicoloured with \(5\) colours, and \(3\)-multicoloured with \(7\) colours. This latter theorem implies the main result of the paper, namely that \(\chi_k(G)\leq\lceil\frac{7k}{3}\rceil\) provided \(G\) is a triangle-free induced subgraph of the planar triangular lattice.