Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
type: Item
instance of: scholarly article
title: Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
zbMATH Open document ID: 0997.05033
DOI: 10.1016/S0012-365X(01)00079-6
author: Frédéric Havet
author: Janez Žerovnik
published in: Discrete Mathematics
publication date: 2002-05-21T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 1743016
zbMATH Keywords: weighted colouring
zbMATH Keywords: hexagonal cells
zbMATH Keywords: triangular lattice
zbMATH Keywords: distributed algorithm
reviewed by: Jozef Fiamčík
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1743016