S. Alouf, E. Altman, J. Galtier, J. Lalande, and C. Touati, Quasi-Optimal Resource Allocation in Multispot MFTDMA Satellite Networks, Combinatorial optimization in communication networks, pp.325-365, 2006.
DOI : 10.1007/0-387-29026-5_13
URL : https://hal.archives-ouvertes.fr/inria-00000005

K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math, vol.21, issue.3, pp.429-490, 1977.
DOI : 10.1090/conm/098
URL : http://projecteuclid.org/download/pdf_1/euclid.bams/1183538218

K. Appel and W. Haken, Every planar map is four colorable, volume 98 of Contemporary Mathematics, 1989.

K. Appel, W. Haken, and J. Koch, Every planar map is four colorable, II. Reducibility. Illinois J. Math, vol.21, issue.3, pp.491-567, 1977.
DOI : 10.1090/conm/098
URL : http://projecteuclid.org/download/pdf_1/euclid.bams/1183538218

K. Cameron, R. Sritharan, and Y. Tang, Finding a maximum induced matching in weakly chordal graphs, The 18th British Combinatorial Conference, pp.133-142, 2001.
DOI : 10.1016/S0012-365X(02)00803-8
URL : http://doi.org/10.1016/s0012-365x(02)00803-8

B. N. Clark, C. J. Colbourn, and D. S. Johnson, Unit disk graphs, Discrete Mathematics, vol.86, issue.1-3, pp.165-177, 1990.
DOI : 10.1016/0012-365X(90)90358-O

L. Cowen, W. Goddard, and C. E. Jesurum, Defective coloring revisited, Journal of Graph Theory, vol.24, issue.3, pp.205-219, 1997.
DOI : 10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T

L. J. Cowen, R. H. Cowen, and D. R. Woodall, Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency, Journal of Graph Theory, vol.1, issue.2, pp.187-195, 1986.
DOI : 10.1002/jgt.3190100207

A. Dessmark, K. Jansen, and A. Lingas, The maximum k-dependent and f-dependent set problem, Algorithms and computation (Hong Kong, pp.88-97, 1993.
DOI : 10.1007/3-540-57568-5_238

H. Djidjev, O. Garrido, C. Levcopoulos, and A. Lingas, On the maximum k-dependent set problem, 1992.

N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. Inst. Combin. Appl, vol.25, pp.79-87, 1999.

U. Fößmeier, G. Kant, and M. Kaufmann, 2-Visibility drawings of planar graphs, Proceedings of Graph Drawing '96, pp.155-168, 1996.
DOI : 10.1007/3-540-62495-3_45

F. Gavril, Algorithms on circular-arc graphs. Networks, pp.357-369, 1974.

M. C. Golumbic, Algorithmic graph theory and perfect graphs, 1980.

A. Gräf, M. Stumpf, and G. Weißenfels, On Coloring Unit Disk Graphs, Algorithmica, vol.20, issue.3, pp.277-293, 1998.
DOI : 10.1007/PL00009196

W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, vol.68, issue.12, pp.1497-1514, 1980.
DOI : 10.1109/PROC.1980.11899

R. B. Hayward, Weakly triangulated graphs, Journal of Combinatorial Theory, Series B, vol.39, issue.3, pp.200-208, 1985.
DOI : 10.1016/0095-8956(85)90050-4

H. B. Hunt, M. V. Iii, V. Marathe, S. S. Radhakrishnan, D. J. Ravi et al., NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs, Journal of Algorithms, vol.26, issue.2, pp.238-274, 1998.
DOI : 10.1006/jagm.1997.0903

R. J. Kang, T. Müller, and J. Sereni, Improper colouring of (random) unit disk graphs, Discrete Mathematics, vol.308, issue.8, 2005.
DOI : 10.1016/j.disc.2007.07.070
URL : https://hal.archives-ouvertes.fr/inria-00070259

R. Leese and S. Hurley, Methods and Algorithms for Radio Channel Assignment, Oxford Lecture Series in Mathematics and Its Applications, 2002.

L. Lovász, On decompositions of graphs, Studia Sci. Math. Hungar, vol.1, pp.237-238, 1966.

E. Malesi´nskamalesi´nska, S. Piskorz, and G. Weißenfels, On the chromatic number of disk graphs, Networks, vol.32, issue.1, pp.13-22, 1998.
DOI : 10.1002/(SICI)1097-0037(199808)32:1<13::AID-NET2>3.0.CO;2-M

M. V. Marathe, H. Breu, H. B. Hunt, I. , S. S. Ravi et al., Simple heuristics for unit disk graphs, Networks, vol.28, issue.2, pp.59-68, 1995.
DOI : 10.1002/net.3230250205

C. Mcdiarmid, Random channel assignment in the plane. Random Structures Algorithms, pp.187-212, 2003.

C. Mcdiarmid and B. Reed, 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

L. Narayanan and S. M. Shende, Static Frequency Assignment in Cellular Networks, Algorithmica, vol.29, issue.3, pp.396-409, 2001.
DOI : 10.1007/s004530010067

S. Olariu, An optimal greedy heuristic to color interval graphs, Information Processing Letters, vol.37, issue.1, pp.21-25, 1991.
DOI : 10.1016/0020-0190(91)90245-D

A. Papakostas and I. G. Tollis, Orthogonal drawing of high degree graphs with small area and few bends, Proceedings of 5th Workshop on Algorithms and Data Structures, pp.354-367, 1998.
DOI : 10.1007/3-540-63307-3_74

. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex