zbMATH — the first resource for mathematics

Finding a five bicolouring of a triangle-free subgraph of the triangular lattice. (English) Zbl 0997.05033
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\).

05C15 Coloring of graphs and hypergraphs
05C90 Applications of graph theory
Full Text: DOI