# zbMATH — the first resource for mathematics

Channel assignment and multicolouring of the induced subgraphs of the triangular lattice. (English) Zbl 0983.05031
Motivated by a real-world problem in mobile telecommunication, the main issue of the paper is a graph multicolouring problem. Let $$G$$ be a finite triangle-free induced subgraph of the planar triangular grid and $$k$$ be a natural number. We want to $$k$$-multicolour $$G$$, that is to assign a set of $$k$$ colours to each vertex of $$G$$ so that adjacent vertices receive disjoint colour-sets. This task resembles the channel assignment problem for transmitters in a mobile telephone network.
The $$[k]$$-chromatic number $$\chi_k(G)$$ of a graph $$G$$ is the least natural number $$n$$ so that there is a $$k$$-multicolouring of $$G$$ using colours only from $$\{1,2,\dots,n\}$$. McDiarmid and Reed conjectured that for any triangle-free induced subgraph $$G$$ of the planar triangular lattice we have $$\chi_k(G)\leq\lceil\frac{9k}{4}\rceil$$ [see C. McDiarmid and B. Reed, Networks 36, No. 2, 114-117 (2000; Zbl 0971.90100)]. To prove the conjecture, it would suffice to prove that any such graph can be $$4$$-multicoloured with only $$9$$ colours. The author proves two weaker statements: any such graph can be $$2$$-multicoloured with $$5$$ colours, and $$3$$-multicoloured with $$7$$ colours. This latter theorem implies the main result of the paper, namely that $$\chi_k(G)\leq\lceil\frac{7k}{3}\rceil$$ provided $$G$$ is a triangle-free induced subgraph of the planar triangular lattice.

##### MSC:
 05C15 Coloring of graphs and hypergraphs 90C35 Programming involving graphs or networks 05C90 Applications of graph theory 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: