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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Finding a five bicolouring of a triangle-free subgraph of the triangular lattice
scientific article

    Statements

    Finding a five bicolouring of a triangle-free subgraph of the triangular lattice (English)
    0 references
    0 references
    0 references
    21 May 2002
    0 references
    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\).
    0 references
    weighted colouring
    0 references
    hexagonal cells
    0 references
    triangular lattice
    0 references
    distributed algorithm
    0 references

    Identifiers