zbMATH — the first resource for mathematics

A technique for multicoloring triangle-free hexagonal graphs. (English) Zbl 1076.05037
Summary: In order to avoid interference in cellular telephone networks, sets of radio frequencies are to be assigned to transmitters such that adjacent transmitters are allotted disjoint sets of frequencies. Often these transmitters are laid out like vertices of a triangular lattice in a plane. This problem corresponds to the problem of multicoloring an induced subgraph of a triangular lattice with integer demands associated with each vertex. We deal with the simpler case of triangle-free subgraphs of the lattice. F. Havet [Discrete Math. 233, No. 1–3, 219–231 (2001; Zbl 0983.05031)] uses inductive arguments to prove that triangle-free hexagonal graphs can be colored with \({7\over 6}\omega_d +o(1)\) colors where \(\omega_d\) is the maximum demand on a clique in the graph. We give a simpler proof and hope that our techniques can be used to prove the conjecture by C. McDiarmid and B. Reed [Networks 36, 114–117 (2000; Zbl 0971.90100)] that these graphs are \({9\over 8}\omega_d +o(1)\)-multicolorable.

05C15 Coloring of graphs and hypergraphs
90B18 Communication networks in operations research
Full Text: DOI
[1] Havet, F., Channel assignment and multicoloring of the induced subgraphs of the triangular lattice, Discrete math., 233, 1-3, (2001)
[2] Havet, F.; Z˘erovnik, J., Finding a five bicolouring of a triangle-free subgraph of the triangular lattice, Discrete math., 244, 103-108, (2002) · Zbl 0997.05033
[3] McDiarmid, C.; Reed, B., Channel assignment and weighted colouring, Networks suppl., 36, 114-117, (2000) · Zbl 0971.90100
[4] S˘parl, P.; Z˘erovnik, J., A 2-local 4/3-competitive algorithm for multicoloring hexagonal graphs, recent trends in graph theory, Algebraic combinatorics and graph algorithms conference, bled, 16, 4-32, (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.