}. and T. ?. {u, })-colouring such that c(v 1 ) = c(t ) If c(v 1 ) = 2, we can colour t 2 with c(v 1 ), since c(t ), c(v ) = c(v 1 ). Then, colouring v 3 with a colour from Z 6 \ {[c(v 1 ), c(v )}, and applying Lemma 19 (b2), we obtain a (G, T )-colouring, a contradiction. So, c(v 1 ) = 2

?. {1, 2. , ?. {{3, 5. , {. et al., (t 1 )] \ {c(t 1 )}) = / 0, then chossing c(t 2 ) in [c(t1)] \ {c(t 1 )} and c(v 3 ) in L(v 3 ) \ [c(t 2 )] (observe that |[c(t 2 )] ? L(v 3 )| ? 2, since L(v 3 ) has no three consecutive integers), and using Lemma 19 (b3), we obtain a (G, T )-colouring, a contradiction If c(t 1 ) = 3, then {c(t ), c(v )} = {4, 6}, and let L(t 2 ) = Z 6 \ {1 Then L(v 2 ) ? ([c(t 1 )] \ {c(t 1 )}) = / 0 this case, colouring t 2 with 3 If c(t 1 ) = 4, then {c(t ), c(v )} = {3, 5}, and if c(t 1 ) = 5, then {c(t ), c(v )} = {4, 6}. In both cases, setting c(t 2 ) = c(t 1 ), choosing c(v 3 ) in Z 6 \ {1, 2, [c(t 1 )]} and using Lemma 19 (a), we obtain a (G, T )-colouring, a contradiction

H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone colourings for networks, Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), pp.2880131-142, 2003.

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.137-152, 2007.
DOI : 10.1002/jgt.20228
URL : http://eprints.eemcs.utwente.nl/secure2/00010334/01/backbone.pdf

H. J. Broersma, J. Fujisawa, L. Marchal, D. Paulusma, A. N. Salman et al., <mml:math altimg="si11.gif" display="inline" 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>??</mml:mi></mml:math>-backbone colorings along pairwise disjoint stars and matchings, Yoshimoto. ?-backbone colorings along pairwise disjoint stars and matchings, pp.5596-5609, 2009.
DOI : 10.1016/j.disc.2008.04.007

Y. Bu and Y. Li, Backbone coloring of planar graphs without special circles, Theoretical Computer Science, vol.412, issue.46, pp.6464-6468, 2011.
DOI : 10.1016/j.tcs.2011.06.032

Y. Bu and S. Zhang, Backbone coloring for C 4 -free planar graphs, Science China Mathematics, vol.41, issue.2, pp.197-206, 2011.

W. Wang, Y. Bu, M. Montassier, and A. Raspaud, On backbone coloring of graphs, Journal of Combinatorial Optimization, vol.17, issue.1, pp.79-93, 2012.
DOI : 10.1007/s10878-010-9342-6
URL : https://hal.archives-ouvertes.fr/lirmm-00782811