Finding a five bicolouring of a triangle-free subgraph of the triangular lattice. (English) Zbl 0997.05033

Havet, Frédéric; Žerovnik, Janez

Discrete Math. 244, No. 1-3, 103-108 (2002).

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\).

Reviewer: Jozef Fiamčík (Prešov)

MSC:

05C15	Coloring of graphs and hypergraphs
05C90	Applications of graph theory

Keywords:

weighted colouring; hexagonal cells; triangular lattice; distributed algorithm