Finding a five bicolouring of a triangle-free subgraph of the triangular lattice (Q1349081)

A basic problem in the design of mobile telephone networks is to assign sets of radio frequency bands (colours) to transmitters (vertices) to avoid interference. An alternative proof of Havet's theorem that every triangle-free induced subgraph of the triangular lattice is 5-bicolourable is given. The proof gives a distributed algorithm which finds a 5-bicolourable triangular lattice of such a graph \(G\). Using this algorithm, there is exhibited a constant time distributed algorithm which finds a \([p]\) colouring of \(G\) with at most \(5\omega_p(G)/4+ 3\) colours, where \(\omega_p\) is the \([p]\) weighted clique number of \(G\).