F. Havet, A. D. King, and M. Liedloff, Ioan Todinca ? (i) In any circular 2-backbone 5-colouring of, vertices x and y receive colours which are cyclically 2 apart

. Further and . Campos, 6] proved that if G is planar and T has diameter at most 3, then BBC 2 (G, T ) ? 5. Hence one can the find the 2-backbone chromatic number of such a pair in polynomial time

G. , C. , F. O. Borodin, and A. N. Glebov, On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph, Conjecture 45, pp.34-53, 2001.

O. V. Borodin, A. N. Glebov, A. R. Raspaud, and M. R. Salavatipour, Planar graphs without cycles of length from 4 to 7 are 3-colorable, Journal of Combinatorial Theory, Series B, vol.93, issue.2, pp.303-311, 2005.
DOI : 10.1016/j.jctb.2004.11.001

URL : https://hal.archives-ouvertes.fr/hal-00307587

H. Broersma, F. V. Fomin, P. A. Golovach, and G. J. Woeginger, Backbone Colorings for Networks, Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), pp.2880131-142, 2003.
DOI : 10.1007/978-3-540-39890-5_12

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, Discrete Mathematics, vol.309, issue.18, pp.5596-5609, 2009.
DOI : 10.1016/j.disc.2008.04.007

V. Campos, F. Havet, R. Sampaio, and A. Silva, Backbone colouring: Tree backbones with small diameter in planar graphs, Theoretical Computer Science, vol.487
DOI : 10.1016/j.tcs.2013.03.003

URL : https://hal.archives-ouvertes.fr/hal-00821608

H. Grötzsch, Ein dreifarbensatz fr dreikreisfreie netze auf der kugel, Math.-Nat. Reihe, vol.8, pp.109-120, 1959.

K. Kawarabayashi and C. Thomassen, Decomposing a planar graph of girth 5 into an independent set and a forest, Journal of Combinatorial Theory, Series B, vol.99, issue.4, pp.674-684, 2009.
DOI : 10.1016/j.jctb.2008.11.002

G. Macgillivray and M. Siggers, On the complexity of <mml:math altimg="si15.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>H</mml:mi></mml:math>-colouring planar graphs, Discrete Mathematics, vol.309, issue.18, pp.5729-5738, 2009.
DOI : 10.1016/j.disc.2008.05.016

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, 1978.
DOI : 10.1145/800133.804350

R. Steinberg, The State of the Three Color Problem, Ann. Discrete Math, vol.55, pp.211-248, 1993.
DOI : 10.1016/S0167-5060(08)70391-1

L. Stockmeyer, Planar 3-colorability is polynomial complete, ACM SIGACT News, vol.5, issue.3, pp.19-25, 1973.
DOI : 10.1145/1008293.1008294