and since GU 1 and GU 2 have maximum degree 1, the colouring we obtain is 1-improper. Then we use 8b colours denoted by (i, j), 1 ? i ? b, 1 ? j ? 8 We give all these colours to the big vertices. Then, for 1 ? j ? 8, we give to each small vertex of U j \ Goof the colours (i, j), 1 ? i ? b. A vertex appears in four of the U j , so each non-goofy vertex receives 4b colours. Finally, by Claim 4, a goofy vertex u has a unique big neigbour v. Thus, there is an integer j such that both u and v are in U j . We assign to u the colours (i, j), 1 ? i ? b. Doing so, each goofy vertex receives b colours. Finally, we use four sets of c colours A t , A d , A l and A r . Each big or quasi-big vertex receives the colours of all these sets and each top (resp. down, left, right) neighbour receives the colours of A t (resp. A d , A l and A r ) This is 1-improper, by Claim 4. Let us now check that ? i+1 ? ? i ? 108. Let v be a vertex. If it is big then n i (v) = a + 8b + 4c; if it is quasi-big, then n i (v) = a + 4b + 4c; if it is goofy, then n i (v) = a + b + c; if it is regular, then n i (v) ? a + 4b, and if, in addition, it is adjacent to a quasi-big vertex, then n i (v) ? a + 4b + c. Hence Quasi-optimal bandwidth allocation for multi-spot MFTDMA satellites, Proc. IEEE INFOCOM 2005, 2005. ,
Channel assignment and multicolouring of the induced subgraphs of the triangular lattice, Discrete Mathematics, vol.233, issue.1-3, pp.219-231, 2001. ,
DOI : 10.1016/S0012-365X(00)00241-7
Improper Colourings of Unit Disk Graphs, Electronic Notes in Discrete Mathematics, vol.22, pp.123-128, 2005. ,
DOI : 10.1016/j.endm.2005.06.022
Improper colourings of unit disk graphs, Networks ,
Finding a five bicolouring of a triangle-free subgraph of the triangular lattice, Discrete Mathematics, vol.244, issue.1-3, pp.103-108, 2002. ,
DOI : 10.1016/S0012-365X(01)00079-6
Graph labeling and radio channel assignment, Journal of Graph Theory, vol.29, issue.4, pp.263-283, 1998. ,
DOI : 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V
Static Frequency Assignment in Cellular Networks, Sirocco 97Proceedings of the 4th international Colloqium on structural information and communication complexity Carleton Scientific pp, pp.215-227, 1997. ,
DOI : 10.1007/s004530010067
Channel assignment and weighted coloring, Networks, vol.29, issue.2, pp.114-117, 2000. ,
DOI : 10.1002/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G
Coloration de graphes et applications, 2006. ,
A technique for multicoloring triangle-free hexagonal graphs, Discrete Mathematics, vol.300, issue.1-3, pp.256-259, 2005. ,
DOI : 10.1016/j.disc.2005.06.002