{. and 3. \. {c, c(v 1 )} because |c(v 1 ) ? c(t )| ? 2, Then by Lemma, vol.19

}. Rv and T. ?{u, By minimality of v 3 }) -colouring which is a (G?{u })-colouring such that c(v ) = 1. Since c(t ), c(v ), c(v 1 ) = 1, we can colour v 3 with 1. Then, colouring t 2 with a colour from Z 6 {1, c(v ), c(t 1 )} and using Lemma 19 (b), we obtain a (G, T )-colouring, a contradiction

}. 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 Lemmacolouring, a contradiction. So, c(v 1 ) = 2

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

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.

A. Proskurowski and M. Syslo, Efficient Vertex- and Edge-Coloring of Outerplanar Graphs, SIAM Journal on Algebraic Discrete Methods, vol.7, issue.1, pp.131-136, 1986.
DOI : 10.1137/0607016

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