N. Alon and J. H. Spencer, The Probabilistic Method, Wiley-Intersci. Ser. Discrete Math. Optim, 2008.

K. Azuma, Weighted sums of certain dependent random variables, Tohoku Mathematical Journal, vol.19, issue.3, pp.357-367, 1967.
DOI : 10.2748/tmj/1178243286

R. Babilon, V. Jelínek, D. , and P. Valtr, Labelings of Graphs with Fixed and Variable Edge-Weights, SIAM Journal on Discrete Mathematics, vol.21, issue.3, pp.688-706, 2007.
DOI : 10.1137/040619545

P. Bella, D. Král-', B. Mohar, and K. Quittnerová, Labeling planar graphs with a condition at distance two, European Journal of Combinatorics, vol.28, issue.8, pp.2201-2239, 2007.
DOI : 10.1016/j.ejc.2007.04.019
URL : https://hal.archives-ouvertes.fr/hal-01184374

H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone colorings for graphs: Tree and path backbones, Journal of Graph Theory, vol.94, issue.2, pp.55-137, 2007.
DOI : 10.1002/jgt.20228

T. Calamoneri, The L(h, k)-Labelling Problem: An Updated Survey and Annotated Bibliography, The Computer Journal, vol.54, issue.8, pp.1344-1371, 2011.
DOI : 10.1093/comjnl/bxr037

G. J. Chang and D. Kuo, The $L(2,1)$-Labeling Problem on Graphs, SIAM Journal on Discrete Mathematics, vol.9, issue.2, pp.309-316, 1996.
DOI : 10.1137/S0895480193245339

P. Erd?-os and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and Finite Sets, pp.609-627, 1975.

J. P. Georges, D. W. Mauro, and M. A. Whittlesey, Relating path coverings to vertex labellings with a condition at distance two, Discrete Mathematics, vol.135, issue.1-3, pp.103-111, 1994.
DOI : 10.1016/0012-365X(93)E0098-O

D. Gonçalves, On the <mml:math altimg="si7.gif" overflow="scroll" xmlns:xocs="http://www.elsevier.com/xml/xocs/dtd" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns="http://www.elsevier.com/xml/ja/dtd" xmlns:ja="http://www.elsevier.com/xml/ja/dtd" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:tb="http://www.elsevier.com/xml/common/table/dtd" xmlns:sb="http://www.elsevier.com/xml/common/struct-bib/dtd" xmlns:ce="http://www.elsevier.com/xml/common/dtd" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:cals="http://www.elsevier.com/xml/common/cals/dtd"><mml:mi mathvariant="normal">L</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>p</mml:mi><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">)</mml:mo></mml:math>-labelling of graphs, Discrete Mathematics, vol.308, issue.8, pp.1405-1414, 2008.
DOI : 10.1016/j.disc.2007.07.075

J. R. Griggs and D. Král, Graph labellings with variable weights, a survey, Discrete Applied Mathematics, vol.157, issue.12, pp.2646-2658, 2009.
DOI : 10.1016/j.dam.2008.08.024

J. R. Griggs and R. K. Yeh, Labelling Graphs with a Condition at Distance 2, SIAM Journal on Discrete Mathematics, vol.5, issue.4, pp.586-595, 1992.
DOI : 10.1137/0405048

A. J. Hoffman and R. R. Singleton, On Moore Graphs with Diameters 2 and 3, IBM Journal of Research and Development, vol.4, issue.5, pp.497-504, 1960.
DOI : 10.1147/rd.45.0497

T. K. Jonas, Graph Coloring Analogues with a Condition at Distance Two: L(2, 1)-Labelings and List ?-Labelings, 1993.

D. and P. Skoda, Bounds for the real number graph labellings and application to labellings of the triangular lattice, SIAM J. Discrete Math, vol.22, pp.1559-1569, 2008.

D. Král and R. Skrekovski, A theorem about the channel assignment problem, SIAM J

D. D. Liu and X. Zhu, Circular Distance Two Labeling and the $\lambda$-Number for Outerplanar Graphs, SIAM Journal on Discrete Mathematics, vol.19, issue.2, pp.281-293, 2005.
DOI : 10.1137/S0895480102414296

C. Mcdiarmid, On the method of bounded differences, Surveys in Combinatorics, pp.148-188, 1989.
DOI : 10.1017/CBO9781107359949.008

C. Mcdiarmid, Concentration for Independent Permutations, Combinatorics, Probability and Computing, vol.11, issue.02, pp.163-178, 2002.
DOI : 10.1017/S0963548301005089

M. Molloy and B. Reed, Colouring graphs when the number of colours is almost the maximum degree, Journal of Combinatorial Theory, Series B, vol.109
DOI : 10.1016/j.jctb.2014.06.004

M. Molloy and B. Reed, Graph Colouring and the Probabilistic Method, Algorithms Combin, vol.23, 2002.
DOI : 10.1007/978-3-642-04016-0

M. Talagrand, Concentration of measure and isoperimetric inequalities in product spaces, Publications math??matiques de l'IH??S, vol.19, issue.158, pp.73-205, 1995.
DOI : 10.1007/BF02699376

J. Van-den-heuvel and S. Mcguinness, Coloring the square of a planar graph, Journal of Graph Theory, vol.7, issue.2, pp.110-124, 2003.
DOI : 10.1002/jgt.10077

R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Mathematics, vol.306, issue.12, pp.1217-1231, 2006.
DOI : 10.1016/j.disc.2005.11.029