Ioan Todinca ? (i) In any circular 2-backbone 5-colouring of, vertices x and y receive colours which are cyclically 2 apart ,
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 ,
On the partition of a planar graph of girth 5 into an empty graph and an acyclic subgraph, Conjecture 45, pp.34-53, 2001. ,
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
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
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
<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
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
Ein dreifarbensatz fr dreikreisfreie netze auf der kugel, Math.-Nat. Reihe, vol.8, pp.109-120, 1959. ,
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
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
The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, 1978. ,
DOI : 10.1145/800133.804350
The State of the Three Color Problem, Ann. Discrete Math, vol.55, pp.211-248, 1993. ,
DOI : 10.1016/S0167-5060(08)70391-1
Planar 3-colorability is polynomial complete, ACM SIGACT News, vol.5, issue.3, pp.19-25, 1973. ,
DOI : 10.1145/1008293.1008294