. Observons-que-d, 2 et d(v ?? , S) ? 2 puisque la règle R3 ne s'est pas appliquée. De plus, aucune feuille libre de T ? ne peut être à distance au 4 ou plus de S, autrement la règle B1 se serait appliquée. Par conséquent, puisque v ? et v ?? sont des noeuds internes, il vient que ni v ? ne peut appartenir à T ? (v ?? )

B. La-règle, Observons que d(v ?? , S) ? 2 puisque la règle R3 ne s'est pas appliquée

F. Si, STOP, cette instance n'admet pas de solution

. Règles-de-branchement, Chaque règle de branchement de l'algorithme crée deux sous-problèmes

|. Pour-une-règle-de-branchement, || O p pour exprimer le fait que l'algorithme crée p instances de sous-problèmes. Le i-ème sous-problème est obtenu en appliquant sur l'instance

B. Existe-une-feuille-libre-v-?-f-de-t-?-vérifiant-d, 4, alors nous distinguons trois cas. (a) S'il existe deux noeuds internes libres v ? , v ?? ? F vérifiant ?(v) = ?(v ? ) = ?(v ?? ) : {ADD(v), RMV({v ? , v ?? })} || RMV(v) (7, 1) (b) S'il existe une feuille libre, v)) (4, 2) (c) S'il existe un unique noeud interne libre v ? ? F de T ? vérifiant ?(v) = ?(v ? ) : {ADD(v), RMV(v ? )} || {RMV(v), ADD(v ? )}}

B. Existe-une-feuille-libre-v-?-f-de-t-?-vérifiant-d, alors nous distinguons quatre cas. (a) S'il existe deux feuilles libres distinctes v ? , v ?? ? F ? {v} de T ? vérifiant ?(v) = ?(v ? ) = ?, ?? ) : {ADD(p(v)), RMV({v ? , v ?? })} || RMV(p(v)) (4

B. Existe-une-feuille-libre-v-?-f-de-t-?-vérifiant-d, alors nous distinguons deux cas. (a) S'il existe k ? 2 sommets libres distincts v 1

A. Adamaszek and M. Adamaszek, Uniqueness of Graph Square Roots of Girth Six, Electronic Journal of Combinatorics, vol.18, 2011.

D. Aingworth, R. Motwani, and F. Harary, The difference between a graph and its square, pp.223-228, 1998.

J. Alber, H. Fernau, and R. Niedermeier, Graph separators: a parameterized view, Journal of Computer and System Sciences, vol.67, issue.4, pp.808-832, 2003.
DOI : 10.1016/S0022-0000(03)00072-2

N. Alon, G. Gutin, E. J. Kim, S. Szeider, and A. Yeo, Solving MAX-r-SATsat Above a Tight Lower Bound, Algorithmica, pp.61-638, 2011.

A. Ambalath, R. Balasundaram, C. Rao, H. , V. Koppula et al., On the Kernelization Complexity of Colorful Motifs, Parameterized and Exact Computation, pp.14-25, 2010.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

S. Arnborg, D. Corneil, and A. Proskurowski, -Tree, SIAM Journal on Algebraic Discrete Methods, vol.8, issue.2, pp.277-284, 1987.
DOI : 10.1137/0608024

S. Arnborg, J. Lagergren, and D. Seese, Easy problems for tree-decomposable graphs, Journal of Algorithms, vol.12, issue.2, pp.308-340, 1991.
DOI : 10.1016/0196-6774(91)90006-K

S. Arora and B. Barak, Computational complexity : a modern approach, 2009.
DOI : 10.1017/CBO9780511804090

G. Bacsó, S. Gravier, A. Gyárfás, M. Preissmann, and A. Sebö, Coloring the Maximal Cliques of Graphs, SIAM Journal on Discrete Mathematics, vol.17, issue.3, pp.361-376, 2004.
DOI : 10.1137/S0895480199359995

J. Bailey, T. Manoukian, and K. Ramamohanarao, A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns, Third IEEE International Conference on Data Mining, p.485, 2003.
DOI : 10.1109/ICDM.2003.1250958

R. Balasubramanian, V. Raman, and V. Yegnanarayanan, On the pseudoachromatic number of join of graphs, International Journal of Computer Mathematics, vol.80, issue.9, pp.1131-1137, 2003.
DOI : 10.1080/00207160310001597206

D. Barth, J. Cohen, and T. Faik, On the b-continuity property of graphs, Discrete Applied Mathematics, vol.155, issue.13, pp.1761-1768, 2007.
DOI : 10.1016/j.dam.2007.04.011

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

R. Beigel and D. Eppstein, 3-coloring in time, Journal of Algorithms, vol.54, issue.2, pp.168-204, 2005.
DOI : 10.1016/j.jalgor.2004.06.008

C. Berge, Hypergraphs : combinatorics of finite sets, 1984.

C. Berge and P. Duchet, Strongly Perfect Graphs, Annals of Discrete Mathematics, vol.21, pp.57-61, 1984.
DOI : 10.1016/S0304-0208(08)72922-0

N. Betzler, R. Van-bevern, M. R. Fellows, C. Komusiewicz, and R. Niedermeier, Parameterized Algorithmics for Finding Connected Motifs in Biological Networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.8, issue.5, pp.1296-1308, 2011.
DOI : 10.1109/TCBB.2011.19

A. Björklund, T. Husfeldt, and M. Koivisto, Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009.
DOI : 10.1137/070683933

H. L. Bodlaender, Achromatic number is NP-complete for cographs and interval graphs, Information Processing Letters, vol.31, issue.3, pp.31-135, 1989.
DOI : 10.1016/0020-0190(89)90221-4

N. Bonichon, C. Gavoille, N. Hanusse, D. Poulalhon, and G. Schaeffer, Planar Graphs, via Well-Orderly Maps and Trees, Graphs and Combinatorics, pp.185-202, 2006.
DOI : 10.1007/s00373-006-0647-2

URL : http://dept-info.labri.fr/~gavoille/article/BGHPS04.pdf

F. Bonomo, G. Duran, F. Maffray, J. Marenco, and M. Valencia-pabon, On the b-Coloring of Cographs and P 4 -Sparse Graphs, Graphs and Combinatorics, pp.153-167, 2009.

L. Cai and D. Juedes, On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, vol.67, issue.4, pp.789-807, 2003.
DOI : 10.1016/S0022-0000(03)00074-6

N. Cairnie and K. Edwards, Some results on the achromatic number, Journal of Graph Theory, vol.26, issue.3, pp.129-136, 1997.
DOI : 10.1002/(SICI)1097-0118(199711)26:3<129::AID-JGT3>3.0.CO;2-T

N. Cairnie and K. Edwards, The achromatic number of bounded degree trees, Discrete Mathematics, vol.188, issue.1-3, pp.87-97, 1998.
DOI : 10.1016/S0012-365X(97)00278-1

M. Cesati, Compendium of Parameterized Problems, 2006.

E. Chambers, B. Kinnersley, N. Prince, and D. West, Extremal Problems for Roman Domination, SIAM Journal on Discrete Mathematics, vol.23, issue.3, pp.1575-1586, 2009.
DOI : 10.1137/070699688

M. Chapelle, M. Cochefert, J. Couturier, D. Kratsch, M. Liedloff et al., Exact Algorithms for Weak Roman Domination, Combinatorial Algorithms, pp.81-93, 2013.
DOI : 10.1007/978-3-642-45278-9_8

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

G. Chapuy, É. Fusy, O. Giménez, B. Mohar, and M. Noy, Asymptotic enumeration and limit laws for graphs of fixed genus, Journal of Combinatorial Theory, Series A, vol.118, issue.3, pp.748-777, 2011.
DOI : 10.1016/j.jcta.2010.11.014

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

M. Chellali, N. Rad, and L. Volkmann, Some results on Roman domination edge critical graphs, AKCE International Journal of Graphs and Combinatorics, vol.9, pp.195-203, 2012.

J. Chen, I. Kanj, J. Meng, G. Xia, and F. Zhang, On the Pseudo-achromatic Number Problem, Graph-Theoretic Concepts in Computer Science, pp.78-89, 2008.
DOI : 10.1007/s10012-000-0129-z

J. Chen, I. Kanj, and G. Xia, Improved Parameterized Upper Bounds for Vertex Cover, Mathematical Foundations of Computer Science Lecture Notes in Computer Science, vol.4162, pp.238-249, 2006.
DOI : 10.1007/11821069_21

J. Chen, Y. Liu, S. Lu, B. O-'sullivan, and I. Razgon, A Fixed-parameter Algorithm for the Directed Feedback Vertex Set Problem, Journal of the ACM, vol.55, issue.21, pp.1-2119, 2008.

C. A. Christen and S. M. Selkow, Some perfect coloring properties of graphs, Journal of Combinatorial Theory, Series B, vol.27, issue.1, pp.49-59, 1979.
DOI : 10.1016/0095-8956(79)90067-4

M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Annals of Mathematics, vol.164, issue.1, pp.51-229, 2006.
DOI : 10.4007/annals.2006.164.51

M. Cochefert, J. Couturier, P. Golovach, D. Kratsch, and D. Paulusma, Sparse Square Roots, Graph-Theoretic Concepts in Computer Science, pp.177-188, 2013.
DOI : 10.1007/978-3-642-45043-3_16

M. Cochefert and D. Kratsch, Exact Algorithms to Clique-Colour Graphs, Theory and Practice of Computer Science Lecture Notes in Computer Science, vol.8327, pp.187-198, 2014.
DOI : 10.1007/978-3-319-04298-5_17

E. Cockayne, O. Favaron, and C. Mynhardt, Secure domination, weak roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl, vol.39, pp.87-100, 2003.

E. Cockayne, P. Grobler, W. Gründlingh, J. Munganga, and J. Van-vuuren, Protection of a Graph, pp.19-32, 2005.

E. Cockayne, P. D. Jr, S. Hedetniemi, and S. Hedetniemi, Roman domination in graphs, Discrete Mathematics, vol.278, issue.1-3, pp.11-22, 2004.
DOI : 10.1016/j.disc.2003.06.004

S. A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing , STOC '71, pp.151-158, 1971.
DOI : 10.1145/800157.805047

D. Corneil, Y. Perl, and L. Stewart, A Linear Recognition Algorithm for Cographs, SIAM Journal on Computing, vol.14, issue.4, pp.926-934, 1985.
DOI : 10.1137/0214065

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, pp.12-75, 1990.
URL : https://hal.archives-ouvertes.fr/hal-00353765

B. Courcelle and J. Engelfriet, Graph Structure and Monadic Second-Order Logic : A Language-Theoretic Approach, 2012.
DOI : 10.1017/CBO9780511977619

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

B. Courcelle, J. A. Makowsky, and U. Rotics, Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width, Theory of Computing Systems, pp.125-150, 2000.

J. Couturier, P. Heggernes, P. Van-'t-hof, and D. Kratsch, Minimal dominating sets in graph classes: Combinatorial bounds and enumeration, Theoretical Computer Science, vol.487, pp.82-94, 2013.
DOI : 10.1016/j.tcs.2013.03.026

M. Cygan, M. Pilipczuk, M. Pilipczuk, and J. Wojtaszczyk, Scheduling Partially Ordered Jobs Faster than 2 n , Algorithmica, pp.68-692, 2014.
DOI : 10.1007/s00453-012-9694-7

D. Défossez, Clique-coloring some classes of odd-hole-free graphs, Journal of Graph Theory, vol.21, issue.3, pp.233-249, 2006.
DOI : 10.1002/jgt.20177

F. Dehne, M. Fellows, M. Langston, F. Rosamond, K. Stevens et al., An O(2 O(k) n 3) FPT Algorithm for??the??Undirected??Feedback??Vertex??Set??Problem, Theory of Computing Systems, issue.2, pp.41-479, 2007.
DOI : 10.1007/11533719_87

E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thilikos, -minor-free graphs, Journal of the ACM, vol.52, issue.6, pp.866-893, 2005.
DOI : 10.1145/1101821.1101823

E. D. Demaine and M. Hajiaghayi, The Bidimensionality Theory and Its Algorithmic Applications, The Computer Journal, vol.51, issue.3, pp.292-302, 2008.
DOI : 10.1093/comjnl/bxm033

H. Djidjev, On the Problem of Partitioning Planar Graphs, SIAM Journal on Algebraic Discrete Methods, vol.3, issue.2, pp.229-240, 1982.
DOI : 10.1137/0603022

H. Djidjev and S. Venkatesan, Planarization of graphs embedded on surfaces, Lecture Notes in Computer Science, vol.1017, pp.62-72, 1995.
DOI : 10.1007/3-540-60618-1_66

R. Dondi, G. Fertin, and S. Vialette, Complexity issues in vertex-colored graph pattern matching, Journal of Discrete Algorithms, vol.9, issue.1, pp.82-99, 2011.
DOI : 10.1016/j.jda.2010.09.002

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

F. Dorn, F. Fomin, and D. Thilikos, Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus, Algorithm Theory -SWAT 2006, pp.172-183, 2006.
DOI : 10.1007/11785293_18

F. Dorn, E. Penninkx, H. Bodlaender, and F. Fomin, Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions, pp.58-790, 2010.
DOI : 10.1007/11561071_11

D. Duffus, B. Sands, N. Sauer, and R. Woodrow, Two-colouring all two-element maximal antichains, Journal of Combinatorial Theory, Series A, vol.57, issue.1, pp.109-116, 1991.
DOI : 10.1016/0097-3165(91)90009-6

K. Edwards and C. Mcdiarmid, New upper bounds on harmonious colorings, Journal of Graph Theory, vol.15, issue.3, pp.257-267, 1994.
DOI : 10.1002/jgt.3190180305

K. Edwards and C. Mcdiarmid, The complexity of harmonious colouring for trees, Discrete Applied Mathematics, vol.57, issue.2-3, pp.133-144, 1995.
DOI : 10.1016/0166-218X(94)00100-R

T. Eiter, G. Gottlob, and K. Makino, New Results on Monotone Dualization and Generating Hypergraph Transversals, SIAM Journal on Computing, vol.32, issue.2, pp.514-537, 2003.
DOI : 10.1137/S009753970240639X

H. Elghazel, V. Deslandres, M. Hacid, A. Dussauchoy, and H. Kheddouci, A New Clustering Approach for Symbolic Data and Its Validation: Application to the Healthcare Data, Foundations of Intelligent Systems, pp.473-482, 2006.
DOI : 10.1007/11875604_54

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

D. Eppstein, Quasiconvex analysis of backtracking algorithms, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pp.788-797, 2004.

P. Erd?s, W. Hare, S. T. Hedetniemi, and R. Laskar, On the equality of the grundy and ochromatic numbers of a graph, Journal of Graph Theory, vol.40, issue.2, pp.157-159, 1987.
DOI : 10.1007/978-1-349-03521-2

P. Erd?s, S. T. Hedetniemi, R. C. Laskar, and G. C. Prins, On the equality of the partial Grundy and upper ochromatic numbers of graphs, Discrete Mathematics, vol.272, issue.1, pp.272-53, 2003.
DOI : 10.1016/S0012-365X(03)00184-5

R. Fagin, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, 1974.

M. Farber, G. Hahn, P. Hell, and D. Miller, Concerning the achromatic number of graphs, Journal of Combinatorial Theory, Series B, vol.40, issue.1, pp.21-39, 1986.
DOI : 10.1016/0095-8956(86)90062-6

B. Farzad and M. Karimi, Square-Root Finding Problem In Graphs, A Complete Dichotomy Theorem, p.7684, 1210.

B. Farzad, L. C. Lau, V. B. Le, and N. N. Tuy, Complexity of Finding Graph Roots with??Girth Conditions, Algorithmica, vol.6, issue.11, pp.62-100, 2012.
DOI : 10.1137/0206036

O. Favaron, K. Karami, R. Khoeilar, and S. Sheikholeslami, On the Roman domination number of a graph, Discrete Mathematics, vol.309, issue.10, pp.3447-3451, 2009.
DOI : 10.1016/j.disc.2008.09.043

M. R. Fellows, G. Fertin, D. Hermelin, and S. Vialette, Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs, Automata, Languages and Programming, pp.340-351, 2007.
DOI : 10.1007/978-3-540-73420-8_31

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

M. R. Fellows, G. Fertin, D. Hermelin, and S. Vialette, Upper and lower bounds for finding connected motifs in vertex-colored graphs, Journal of Computer and System Sciences, vol.77, issue.4, pp.77-799, 2011.
DOI : 10.1016/j.jcss.2010.07.003

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

J. Flum and M. Grohe, Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, 2006.

F. Fomin, S. Gaspers, D. Kratsch, M. Liedloff, and S. Saurabh, Iterative Compression and Exact Algorithms, Mathematical Foundations of Computer Science, pp.335-346, 2008.
DOI : 10.1007/978-3-540-85238-4_27

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

F. Fomin, S. Gaspers, and S. Saurabh, Improved Exact Algorithms for Counting 3- and 4-Colorings, Computing and Combinatorics, pp.65-74, 2007.
DOI : 10.1007/978-3-540-73545-8_9

F. Fomin, F. Grandoni, and D. Kratsch, Measure and Conquer: Domination ??? A Case Study, Automata, Languages and Programming, pp.191-203, 2005.
DOI : 10.1007/11523468_16

F. Fomin, F. Grandoni, and D. Kratsch, A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM, vol.56, issue.5, 2009.
DOI : 10.1145/1552285.1552286

F. Fomin, D. Kratsch, and G. Woeginger, Exact (Exponential) Algorithms for the Dominating Set Problem, Graph-Theoretic Concepts in Computer Science, pp.245-256, 2005.
DOI : 10.1007/978-3-540-30559-0_21

F. Fomin and D. Thilikos, A Simple and Fast Approach for Solving Problems on Planar Graphs, STACS 2004, pp.56-67, 2004.
DOI : 10.1007/978-3-540-24749-4_6

F. Fomin and D. Thilikos, Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up, Automata, Languages and Programming, pp.581-592, 2004.
DOI : 10.1007/978-3-540-27836-8_50

F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov, Combinatorial bounds via measure and conquer, ACM Transactions on Algorithms, vol.5, issue.1, pp.1-917, 2008.
DOI : 10.1145/1435375.1435384

F. V. Fomin and D. M. Thilikos, New upper bounds on the decomposability of planar graphs, Journal of Graph Theory, vol.14, issue.1, pp.53-81, 2006.
DOI : 10.1007/978-1-4612-0515-9

D. Fulkerson and O. Gross, Incidence matrices and interval graphs, Pacific journal of mathematics, pp.835-855, 1965.

D. Gaceb, V. Eglin, F. Lebourgeois, H. Emptoz, and H. Emptoz, Graph b-Coloring for Automatic Recognition of Documents, ICDAR '09, 10th International Conference on Document Analysis and Recognition, pp.261-265, 2009.

M. R. Garey and D. S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979.

S. Gaspers, Algorithmes exponentiels, master's thesis, 2005.

S. Gaspers, Exponential Time Algorithms : Structures, Measures, and Bounds, 2010.

S. Gaspers, D. Kratsch, and M. Liedloff, On Independent Sets and Bicliques in Graphs, Graph-Theoretic Concepts in Computer Science, pp.171-182, 2008.
DOI : 10.1007/978-3-540-79723-4_19

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

J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, vol.5, issue.3, pp.391-407, 1984.
DOI : 10.1016/0196-6774(84)90019-1

W. Goddard, S. Hedetniemi, and S. Hedetniemi, Eternal Security in Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.52, pp.160-180, 2005.

J. Goldwasser and W. Klostermeyer, Tight bounds for eternal dominating sets in graphs, Discrete Mathematics, vol.308, issue.12, pp.2589-2593, 2008.
DOI : 10.1016/j.disc.2007.06.005

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, 2004.

P. Grobler and C. Mynhardt, Secure domination critical graphs, Discrete Mathematics, vol.309, issue.19, pp.5820-5827, 2009.
DOI : 10.1016/j.disc.2008.05.050

URL : https://doi.org/10.1016/j.disc.2008.05.050

S. Guillemot and F. Sikora, Finding and Counting Vertex-Colored Subtrees, Algorithmica, pp.65-828, 2013.
DOI : 10.1007/978-3-642-15155-2_36

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

J. Guo, J. Gramm, F. Hüffner, R. Niedermeier, and S. Wernicke, Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization, Journal of Computer and System Sciences, vol.72, issue.8, pp.72-1386, 2006.
DOI : 10.1016/j.jcss.2006.02.001

R. P. Gupta, Bounds on the chromatic and achromatic numbers of complementary graphs, Recent Progress in Combinatorics, pp.229-235, 1969.

M. Hagen, Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, vol.157, issue.7, pp.1460-1469, 2009.
DOI : 10.1016/j.dam.2008.10.004

F. Harary and S. Hedetniemi, The achromatic number of a graph, Journal of Combinatorial Theory, vol.8, issue.2, pp.154-161, 1970.
DOI : 10.1016/S0021-9800(70)80072-2

F. Havet, C. L. Sales, and L. Sampaio, b-coloring of tight graphs, Discrete Applied Mathematics, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00468734

F. Havet and L. Sampaio, On the Grundy and b-Chromatic Numbers of a Graph, Algorithmica, vol.306, issue.23, pp.65-885, 2013.
DOI : 10.1016/j.disc.2005.06.044

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

T. Haynes, S. Hedetniemi, and P. Slater, Domination in Graphs, of Pure and Applied Mathematics, 1998.
DOI : 10.1201/b16132-65

M. Henning and S. Hedetniemi, Defending the Roman Empire???A new strategy, Discrete Mathematics, vol.266, issue.1-3, pp.239-251, 2003.
DOI : 10.1016/S0012-365X(02)00811-7

F. Hüffner, C. Komusiewicz, H. Moser, and R. Niedermeier, Fixed-Parameter Algorithms for Cluster Vertex Deletion, Theory of Computing Systems, pp.47-196, 2010.

J. Hopcroft and M. Krishnamoorthy, On the Harmonious Coloring of Graphs, SIAM Journal on Algebraic Discrete Methods, vol.4, issue.3, pp.306-311, 1983.
DOI : 10.1137/0604032

J. Hopcroft and R. Tarjan, Efficient Planarity Testing, Journal of the ACM, vol.21, issue.4, pp.549-568, 1974.
DOI : 10.1145/321850.321852

W. Hsu, Recognizing planar perfect graphs, Journal of the ACM, vol.34, issue.2, pp.255-288, 1987.
DOI : 10.1145/23005.31330

R. Impagliazzo and R. Paturi, On the Complexity of k-SAT, Journal of Computer and System Sciences, vol.62, issue.2, pp.367-375, 2001.
DOI : 10.1006/jcss.2000.1727

R. W. Irving and D. F. Manlove, The b-chromatic number of a graph, Discrete Applied Mathematics, vol.91, issue.1-3, pp.127-141, 1999.
DOI : 10.1016/S0166-218X(98)00146-2

Y. Iwata, A Faster Algorithm for Dominating Set Analyzed by the Potential Method, Proceedings of the 11th International Symposium on Parameterized and Exact Computation, pp.41-54, 2012.
DOI : 10.1016/j.jalgor.2004.01.001

M. Jakovac and S. Klav?ar, The b-Chromatic Number of Cubic Graphs, Graphs and Combinatorics, vol.306, issue.1, pp.107-118, 2010.
DOI : 10.1080/09720529.2005.10698024

R. Karp, Reducibility among Combinatorial Problems, in Complexity of Computer Computations , The IBM Research Symposia Series, pp.85-103, 1972.

D. J. Kavvadias and E. C. Stavropoulos, An Efficient Algorithm for the Transversal Hypergraph Generation, Journal of Graph Algorithms and Applications, vol.9, issue.2, pp.239-264, 2005.
DOI : 10.7155/jgaa.00107

K. Kawarabayashi, B. Mohar, and B. Reed, A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width, 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp.771-780, 2008.
DOI : 10.1109/FOCS.2008.53

S. Klein and A. Morgana, On clique-colouring of graphs with few P4???s, Journal of the Brazilian Computer Society, vol.6, issue.2, pp.113-119, 2012.
DOI : 10.1016/S0012-365X(98)00319-7

D. König, Theory of Finite and Infinite Graphs, Theory of Finite and Infinite Graphs, pp.45-421, 1990.

E. Korach and N. Solel, Tree-width, path-width, and cutwidth, Discrete Applied Mathematics, vol.43, issue.1, pp.97-101, 1993.
DOI : 10.1016/0166-218X(93)90171-J

G. Kortsarz, J. Radhakrishnan, and S. Sivasubramanian, Complete partitions of graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '05, pp.860-869, 2005.

M. Kouider and M. Zaker, Bounds for the b-chromatic number of some families of graphs, Discrete Mathematics, vol.306, issue.7, pp.617-623, 2006.
DOI : 10.1016/j.disc.2006.01.012

J. Kratochvíl and Z. Tuza, On the complexity of bicoloring clique hypergraphs of graphs, Journal of Algorithms, vol.45, issue.1, pp.40-54, 2002.
DOI : 10.1016/S0196-6774(02)00221-3

J. Kratochvíl, Z. Tuza, and M. Voigt, On the b-Chromatic Number of Graphs, Graph- Theoretic Concepts in Computer Science, pp.310-320, 2002.
DOI : 10.1007/3-540-36379-3_27

C. Kuratowski, Sur le probl??me des courbes gauches en Topologie, Fundamenta Mathematicae, vol.15, pp.271-283, 1930.
DOI : 10.4064/fm-15-1-271-283

V. Lacroix, C. G. Fernandes, and M. Sagot, Motif Search in Graphs: Application to Metabolic Networks, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.3, issue.4, pp.360-368, 2006.
DOI : 10.1109/TCBB.2006.55

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

L. C. Lau, Bipartite roots of graphs, ACM Transactions on Algorithms, vol.2, issue.2, pp.178-208, 2006.
DOI : 10.1145/1150334.1150337

L. C. Lau and D. G. , Recognizing Powers of Proper Interval, Split, and Chordal Graphs, SIAM Journal on Discrete Mathematics, vol.18, issue.1, pp.83-102, 2004.
DOI : 10.1137/S0895480103425930

E. L. Lawler, A note on the complexity of the chromatic number problem, Information Processing Letters, vol.5, issue.3, pp.66-67, 1976.
DOI : 10.1016/0020-0190(76)90065-X

V. B. Le and N. N. Tuy, The square of a block graph, Discrete Mathematics, vol.310, issue.4, pp.310-734, 2010.
DOI : 10.1016/j.disc.2009.09.004

J. Lee and Y. Shin, The achromatic number of the union of cycles, Discrete Applied Mathematics, vol.143, issue.1-3, pp.330-335, 2004.
DOI : 10.1016/j.dam.2003.12.002

S. Lee and J. Mitchem, An upper bound for the harmonious chromatic number of a graph, Journal of Graph Theory, vol.4, issue.4, pp.565-567, 1987.
DOI : 10.1002/jgt.3190110414

C. E. Leiserson, R. L. Rivest, C. Stein, and T. H. Cormen, Introduction to algorithms, 2001.

M. Liedloff, Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : domination , variantes et généralisations, phd thesis, Laboratoire d'Informatique Théorique et Appliquée, 2007.

M. Liedloff, T. Kloks, J. Liu, and S. Peng, Efficient algorithms for Roman domination on some classes of graphs, Discrete Applied Mathematics, vol.156, issue.18, pp.3400-3415, 2008.
DOI : 10.1016/j.dam.2008.01.011

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

Y. Lin and S. Skiena, Algorithms for Square Roots of Graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.1, pp.99-118, 1995.
DOI : 10.1137/S089548019120016X

R. Lipton and R. Tarjan, A Separator Theorem for Planar Graphs, SIAM Journal on Applied Mathematics, vol.36, issue.2, pp.177-189, 1979.
DOI : 10.1137/0136016

C. Liu and G. Chang, Roman Domination on 2-Connected Graphs, SIAM Journal on Discrete Mathematics, vol.26, issue.1, pp.193-205, 2012.
DOI : 10.1137/080733085

L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Mathematics, vol.2, issue.3, pp.253-267, 1972.
DOI : 10.1016/0012-365X(72)90006-4

G. Macgillivray and A. Rodriguez, The achromatic number of the union of paths, Discrete Mathematics, vol.231, issue.1-3, pp.331-335, 2001.
DOI : 10.1016/S0012-365X(00)00330-7

D. Marx, Complexity of clique coloring and related problems, Theoretical Computer Science, vol.412, issue.29, pp.3487-3500, 2011.
DOI : 10.1016/j.tcs.2011.02.038

A. Máté, A lower estimate for the achromatic number of irreducible graphs, Discrete Mathematics, vol.33, issue.2, pp.171-183, 1981.
DOI : 10.1016/0012-365X(81)90164-3

A. Maury, Énumération des dominants minimaux d'un graphe, 2013.

F. Mcmorris, T. Warnow, and T. Wimer, Triangulating Vertex-Colored Graphs, SIAM Journal on Discrete Mathematics, vol.7, issue.2, pp.296-306, 1994.
DOI : 10.1137/S0895480192229273

M. Milanic and O. Schaudt, Computing square roots of trivially perfect and threshold graphs, Discrete Applied Mathematics, vol.161, issue.10-11
DOI : 10.1016/j.dam.2012.12.027

G. Miller, Isomorphism testing for graphs of bounded genus, Proceedings of the twelfth annual ACM symposium on Theory of computing , STOC '80, pp.225-235, 1980.
DOI : 10.1145/800141.804670

Z. Miller and D. Pritikin, The harmonious coloring number of a graph, Discrete Mathematics, vol.93, issue.2-3, pp.211-228, 1991.
DOI : 10.1016/0012-365X(91)90257-3

J. Mitchem, On the Harmonious Chromatic Number of a Graph, Graph Colouring and Variations, pp.151-157, 1989.
DOI : 10.1016/S0167-5060(08)70307-8

B. Mohar and R. Skrekovski, The Grötzsch Theorem for the hypergraph of maximal cliques, Electronic Journal of Combinatorics, vol.6, p.2, 1999.

J. Moon and L. Moser, On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965.
DOI : 10.1007/BF02760024

R. Motwani and M. Sudan, Computing roots of graphs is hard, Discrete Applied Mathematics, vol.54, issue.1, pp.81-88, 1994.
DOI : 10.1016/0166-218X(94)00023-9

A. Mukhopadhyay, The square root of a graph, Journal of Combinatorial Theory, vol.2, issue.3, pp.290-295, 1967.
DOI : 10.1016/S0021-9800(67)80030-9

S. Nakano and T. Uno, Constant Time Generation of Trees with Specified Diameter, Graph-Theoretic Concepts in Computer Science, pp.33-45, 2005.
DOI : 10.1007/978-3-540-30559-0_3

J. Nederlof, Fast Polynomial-Space Algorithms Using Inclusion-Exclusion, Algorithmica, pp.65-868, 2013.

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, of Oxford Lecture Series in Mathematics and its Applications, 2006.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

R. Niedermeier and P. Rossmanith, A general method to speed up fixed-parameter-tractable algorithms, Information Processing Letters, vol.73, issue.3-4, pp.125-129, 2000.
DOI : 10.1016/S0020-0190(00)00004-1

M. Rao, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Theoretical Computer Science, vol.377, issue.1-3, pp.260-267, 2007.
DOI : 10.1016/j.tcs.2007.03.043

URL : https://hal.archives-ouvertes.fr/lirmm-00204064

C. Revelle and K. Rosing, Defendens Imperium Romanum: A Classical Problem in Military Strategy, The American Mathematical Monthly, vol.107, issue.7, pp.585-594, 2000.
DOI : 10.2307/2589113

R. Rizzi and F. Sikora, Some Results on more Flexible Versions of Graph Motif, Computer Science -Theory and Applications Lecture Notes in Computer Science, vol.7353, pp.278-289, 2012.
DOI : 10.1007/978-3-642-30642-6_26

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

N. Robertson, D. Sanders, P. Seymour, and R. Thomas, The Four-Colour Theorem, Journal of Combinatorial Theory, Series B, vol.70, issue.1, pp.2-44, 1997.
DOI : 10.1006/jctb.1997.1750

N. Robertson and P. Seymour, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, vol.35, issue.1, pp.39-61, 1983.
DOI : 10.1016/0095-8956(83)90079-5

N. Robertson and P. Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory, Series B, vol.52, issue.2, pp.153-190, 1991.
DOI : 10.1016/0095-8956(91)90061-N

J. Robson, Algorithms for maximum independent sets, Journal of Algorithms, vol.7, issue.3, pp.425-440, 1986.
DOI : 10.1016/0196-6774(86)90032-5

J. M. Robson, Finding a maximum independent set in time O(2 n/4 ). https

D. Rose, R. Tarjan, and G. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, SIAM Journal on Computing, vol.5, issue.2, pp.266-283, 1976.
DOI : 10.1137/0205021

I. C. Ross and F. Harary, The Square of a Tree, Bell System Technical Journal, vol.39, issue.3, pp.641-647, 1960.
DOI : 10.1002/j.1538-7305.1960.tb03936.x

G. F. Royle, Counting Set Covers and Split Graphs, Journal of Integer Sequences, vol.3, p.3, 2000.

P. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, vol.32, issue.2, pp.14-217, 1994.
DOI : 10.1007/BF01215352

Z. Shi, W. Goddard, S. T. Hedetniemi, K. Kennedy, R. Laskar et al., An algorithm for partial Grundy number on trees, Discrete Mathematics, vol.304, issue.1-3, pp.108-116, 2005.
DOI : 10.1016/j.disc.2005.09.008

I. Stewart, Defend the Roman Empire!, Scientific American, vol.281, issue.6, pp.136-139, 1999.
DOI : 10.1038/scientificamerican1299-136

J. Telle and A. Proskurowski, Algorithms for Vertex Partitioning Problems on Partial k-Trees, SIAM Journal on Discrete Mathematics, vol.10, issue.4, pp.529-550, 1997.
DOI : 10.1137/S0895480194275825

C. Thomassen, The graph genus problem is NP-complete, Journal of Algorithms, vol.10, issue.4, pp.568-576, 1989.
DOI : 10.1016/0196-6774(89)90006-0

S. Tsukiyama, M. Ide, H. Ariyoshi, and I. Shirakawa, A New Algorithm for Generating All the Maximal Independent Sets, SIAM Journal on Computing, vol.6, issue.3, pp.505-517, 1977.
DOI : 10.1137/0206036

J. Van-rooij, Exact exponential-time algorithms for domination problems in graphs, phd thesis, 2011.

J. Van-rooij and H. Bodlaender, Exact algorithms for dominating set, Discrete Applied Mathematics, vol.159, issue.17, pp.2147-2164, 2011.
DOI : 10.1016/j.dam.2011.07.001

J. Van-rooij, J. Nederlof, and T. Van-dijk, Inclusion/Exclusion Meets Measure and Conquer, Algorithms -ESA 2009, pp.554-565, 2009.
DOI : 10.1007/978-3-642-04128-0_51

M. Wahlström, Exact algorithms for finding minimum transversals in rank-3 hypergraphs, Journal of Algorithms, vol.51, issue.2, pp.107-121, 2004.
DOI : 10.1016/j.jalgor.2004.01.001

G. Woeginger, Exact Algorithms for NP-Hard Problems: A Survey, Combinatorial Optimization -Eureka, pp.185-207, 2003.
DOI : 10.1007/3-540-36478-1_17

M. Xiao and H. Nagamochi, Exact Algorithms for Maximum Independent Set, CoRR, abs/1312, p.6260, 2013.

H. Xing, X. Chen, and X. Chen, A note on Roman domination in graphs, Discrete Mathematics, vol.306, issue.24, pp.3338-3340, 2006.
DOI : 10.1016/j.disc.2006.06.018

M. Yannakakis and F. Gavril, Edge Dominating Sets in Graphs, SIAM Journal on Applied Mathematics, vol.38, issue.3, pp.364-372, 1980.
DOI : 10.1137/0138030

V. Yegnanarayanan, The Pseudoachromatic Number of a Graph, Southeast Asian Bulletin of Mathematics, vol.24, issue.1, pp.129-136, 2000.
DOI : 10.1007/s10012-000-0129-z

V. Yegnanarayanan, Graph colourings and partitions, Theoretical Computer Science, vol.263, issue.1-2, pp.59-74, 2001.
DOI : 10.1016/S0304-3975(00)00231-0

URL : https://doi.org/10.1016/s0304-3975(00)00231-0

M. Zaker, Results on the Grundy chromatic number of graphs, Discrete Mathematics, vol.306, issue.23, pp.3166-3173, 2006.
DOI : 10.1016/j.disc.2005.06.044

V. Zemlyachenko, N. Korneenko, and R. Tyshkevich, Graph isomorphism problem, Journal of Soviet Mathematics, vol.9, issue.No. 2, pp.1426-1481, 1985.
DOI : 10.1145/322123.322125