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 ?? ) ,
Observons que d(v ?? , S) ? 2 puisque la règle R3 ne s'est pas appliquée ,
STOP, cette instance n'admet pas de solution ,
Chaque règle de branchement de l'algorithme crée deux sous-problèmes ,
|| 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 ,
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 ? )}} ,
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 ,
alors nous distinguons deux cas. (a) S'il existe k ? 2 sommets libres distincts v 1 ,
Uniqueness of Graph Square Roots of Girth Six, Electronic Journal of Combinatorics, vol.18, 2011. ,
The difference between a graph and its square, pp.223-228, 1998. ,
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
Solving MAX-r-SATsat Above a Tight Lower Bound, Algorithmica, pp.61-638, 2011. ,
On the Kernelization Complexity of Colorful Motifs, Parameterized and Exact Computation, pp.14-25, 2010. ,
DOI : 10.1093/acprof:oso/9780198566076.001.0001
-Tree, SIAM Journal on Algebraic Discrete Methods, vol.8, issue.2, pp.277-284, 1987. ,
DOI : 10.1137/0608024
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
Computational complexity : a modern approach, 2009. ,
DOI : 10.1017/CBO9780511804090
Coloring the Maximal Cliques of Graphs, SIAM Journal on Discrete Mathematics, vol.17, issue.3, pp.361-376, 2004. ,
DOI : 10.1137/S0895480199359995
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
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
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
3-coloring in time, Journal of Algorithms, vol.54, issue.2, pp.168-204, 2005. ,
DOI : 10.1016/j.jalgor.2004.06.008
Hypergraphs : combinatorics of finite sets, 1984. ,
Strongly Perfect Graphs, Annals of Discrete Mathematics, vol.21, pp.57-61, 1984. ,
DOI : 10.1016/S0304-0208(08)72922-0
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
Set Partitioning via Inclusion-Exclusion, SIAM Journal on Computing, vol.39, issue.2, pp.546-563, 2009. ,
DOI : 10.1137/070683933
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
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
On the b-Coloring of Cographs and P 4 -Sparse Graphs, Graphs and Combinatorics, pp.153-167, 2009. ,
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
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
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
Compendium of Parameterized Problems, 2006. ,
Extremal Problems for Roman Domination, SIAM Journal on Discrete Mathematics, vol.23, issue.3, pp.1575-1586, 2009. ,
DOI : 10.1137/070699688
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
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
Some results on Roman domination edge critical graphs, AKCE International Journal of Graphs and Combinatorics, vol.9, pp.195-203, 2012. ,
On the Pseudo-achromatic Number Problem, Graph-Theoretic Concepts in Computer Science, pp.78-89, 2008. ,
DOI : 10.1007/s10012-000-0129-z
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
A Fixed-parameter Algorithm for the Directed Feedback Vertex Set Problem, Journal of the ACM, vol.55, issue.21, pp.1-2119, 2008. ,
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
The strong perfect graph theorem, Annals of Mathematics, vol.164, issue.1, pp.51-229, 2006. ,
DOI : 10.4007/annals.2006.164.51
Sparse Square Roots, Graph-Theoretic Concepts in Computer Science, pp.177-188, 2013. ,
DOI : 10.1007/978-3-642-45043-3_16
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
Secure domination, weak roman domination and forbidden subgraphs, Bull. Inst. Combin. Appl, vol.39, pp.87-100, 2003. ,
Protection of a Graph, pp.19-32, 2005. ,
Roman domination in graphs, Discrete Mathematics, vol.278, issue.1-3, pp.11-22, 2004. ,
DOI : 10.1016/j.disc.2003.06.004
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
A Linear Recognition Algorithm for Cographs, SIAM Journal on Computing, vol.14, issue.4, pp.926-934, 1985. ,
DOI : 10.1137/0214065
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
Graph Structure and Monadic Second-Order Logic : A Language-Theoretic Approach, 2012. ,
DOI : 10.1017/CBO9780511977619
URL : https://hal.archives-ouvertes.fr/hal-00646514
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width, Theory of Computing Systems, pp.125-150, 2000. ,
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
Scheduling Partially Ordered Jobs Faster than 2 n , Algorithmica, pp.68-692, 2014. ,
DOI : 10.1007/s00453-012-9694-7
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
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
-minor-free graphs, Journal of the ACM, vol.52, issue.6, pp.866-893, 2005. ,
DOI : 10.1145/1101821.1101823
The Bidimensionality Theory and Its Algorithmic Applications, The Computer Journal, vol.51, issue.3, pp.292-302, 2008. ,
DOI : 10.1093/comjnl/bxm033
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
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
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
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
Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions, pp.58-790, 2010. ,
DOI : 10.1007/11561071_11
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
New upper bounds on harmonious colorings, Journal of Graph Theory, vol.15, issue.3, pp.257-267, 1994. ,
DOI : 10.1002/jgt.3190180305
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
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
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
Quasiconvex analysis of backtracking algorithms, Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pp.788-797, 2004. ,
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
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
Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings, 1974. ,
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
Square-Root Finding Problem In Graphs, A Complete Dichotomy Theorem, p.7684, 1210. ,
Complexity of Finding Graph Roots with??Girth Conditions, Algorithmica, vol.6, issue.11, pp.62-100, 2012. ,
DOI : 10.1137/0206036
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
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
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
Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, 2006. ,
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
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
Measure and Conquer: Domination ??? A Case Study, Automata, Languages and Programming, pp.191-203, 2005. ,
DOI : 10.1007/11523468_16
A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM, vol.56, issue.5, 2009. ,
DOI : 10.1145/1552285.1552286
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
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
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
Combinatorial bounds via measure and conquer, ACM Transactions on Algorithms, vol.5, issue.1, pp.1-917, 2008. ,
DOI : 10.1145/1435375.1435384
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
Incidence matrices and interval graphs, Pacific journal of mathematics, pp.835-855, 1965. ,
Graph b-Coloring for Automatic Recognition of Documents, ICDAR '09, 10th International Conference on Document Analysis and Recognition, pp.261-265, 2009. ,
Computers and Intractability : A Guide to the Theory of NP-Completeness, 1979. ,
Algorithmes exponentiels, master's thesis, 2005. ,
Exponential Time Algorithms : Structures, Measures, and Bounds, 2010. ,
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
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
Eternal Security in Graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.52, pp.160-180, 2005. ,
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
Algorithmic Graph Theory and Perfect Graphs, 2004. ,
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
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
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
Bounds on the chromatic and achromatic numbers of complementary graphs, Recent Progress in Combinatorics, pp.229-235, 1969. ,
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
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
b-coloring of tight graphs, Discrete Applied Mathematics, 2011. ,
URL : https://hal.archives-ouvertes.fr/inria-00468734
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
Domination in Graphs, of Pure and Applied Mathematics, 1998. ,
DOI : 10.1201/b16132-65
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
Fixed-Parameter Algorithms for Cluster Vertex Deletion, Theory of Computing Systems, pp.47-196, 2010. ,
On the Harmonious Coloring of Graphs, SIAM Journal on Algebraic Discrete Methods, vol.4, issue.3, pp.306-311, 1983. ,
DOI : 10.1137/0604032
Efficient Planarity Testing, Journal of the ACM, vol.21, issue.4, pp.549-568, 1974. ,
DOI : 10.1145/321850.321852
Recognizing planar perfect graphs, Journal of the ACM, vol.34, issue.2, pp.255-288, 1987. ,
DOI : 10.1145/23005.31330
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
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
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
The b-Chromatic Number of Cubic Graphs, Graphs and Combinatorics, vol.306, issue.1, pp.107-118, 2010. ,
DOI : 10.1080/09720529.2005.10698024
Reducibility among Combinatorial Problems, in Complexity of Computer Computations , The IBM Research Symposia Series, pp.85-103, 1972. ,
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
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
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
Theory of Finite and Infinite Graphs, Theory of Finite and Infinite Graphs, pp.45-421, 1990. ,
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
Complete partitions of graphs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '05, pp.860-869, 2005. ,
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
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
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
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
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
Bipartite roots of graphs, ACM Transactions on Algorithms, vol.2, issue.2, pp.178-208, 2006. ,
DOI : 10.1145/1150334.1150337
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
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
The square of a block graph, Discrete Mathematics, vol.310, issue.4, pp.310-734, 2010. ,
DOI : 10.1016/j.disc.2009.09.004
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
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
Introduction to algorithms, 2001. ,
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. ,
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
Algorithms for Square Roots of Graphs, SIAM Journal on Discrete Mathematics, vol.8, issue.1, pp.99-118, 1995. ,
DOI : 10.1137/S089548019120016X
A Separator Theorem for Planar Graphs, SIAM Journal on Applied Mathematics, vol.36, issue.2, pp.177-189, 1979. ,
DOI : 10.1137/0136016
Roman Domination on 2-Connected Graphs, SIAM Journal on Discrete Mathematics, vol.26, issue.1, pp.193-205, 2012. ,
DOI : 10.1137/080733085
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
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
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 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
Énumération des dominants minimaux d'un graphe, 2013. ,
Triangulating Vertex-Colored Graphs, SIAM Journal on Discrete Mathematics, vol.7, issue.2, pp.296-306, 1994. ,
DOI : 10.1137/S0895480192229273
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
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
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
On the Harmonious Chromatic Number of a Graph, Graph Colouring and Variations, pp.151-157, 1989. ,
DOI : 10.1016/S0167-5060(08)70307-8
The Grötzsch Theorem for the hypergraph of maximal cliques, Electronic Journal of Combinatorics, vol.6, p.2, 1999. ,
On cliques in graphs, Israel Journal of Mathematics, vol.3, issue.1, pp.23-28, 1965. ,
DOI : 10.1007/BF02760024
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
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
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
Fast Polynomial-Space Algorithms Using Inclusion-Exclusion, Algorithmica, pp.65-868, 2013. ,
Invitation to Fixed-Parameter Algorithms, of Oxford Lecture Series in Mathematics and its Applications, 2006. ,
DOI : 10.1093/acprof:oso/9780198566076.001.0001
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
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
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
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
The Four-Colour Theorem, Journal of Combinatorial Theory, Series B, vol.70, issue.1, pp.2-44, 1997. ,
DOI : 10.1006/jctb.1997.1750
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
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
Algorithms for maximum independent sets, Journal of Algorithms, vol.7, issue.3, pp.425-440, 1986. ,
DOI : 10.1016/0196-6774(86)90032-5
Finding a maximum independent set in time O(2 n/4 ). https ,
Algorithmic Aspects of Vertex Elimination on Graphs, SIAM Journal on Computing, vol.5, issue.2, pp.266-283, 1976. ,
DOI : 10.1137/0205021
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
Counting Set Covers and Split Graphs, Journal of Integer Sequences, vol.3, p.3, 2000. ,
Call routing and the ratcatcher, Combinatorica, vol.32, issue.2, pp.14-217, 1994. ,
DOI : 10.1007/BF01215352
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
Defend the Roman Empire!, Scientific American, vol.281, issue.6, pp.136-139, 1999. ,
DOI : 10.1038/scientificamerican1299-136
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
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
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
Exact exponential-time algorithms for domination problems in graphs, phd thesis, 2011. ,
Exact algorithms for dominating set, Discrete Applied Mathematics, vol.159, issue.17, pp.2147-2164, 2011. ,
DOI : 10.1016/j.dam.2011.07.001
Inclusion/Exclusion Meets Measure and Conquer, Algorithms -ESA 2009, pp.554-565, 2009. ,
DOI : 10.1007/978-3-642-04128-0_51
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
Exact Algorithms for NP-Hard Problems: A Survey, Combinatorial Optimization -Eureka, pp.185-207, 2003. ,
DOI : 10.1007/3-540-36478-1_17
Exact Algorithms for Maximum Independent Set, CoRR, abs/1312, p.6260, 2013. ,
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
Edge Dominating Sets in Graphs, SIAM Journal on Applied Mathematics, vol.38, issue.3, pp.364-372, 1980. ,
DOI : 10.1137/0138030
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
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
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
Graph isomorphism problem, Journal of Soviet Mathematics, vol.9, issue.No. 2, pp.1426-1481, 1985. ,
DOI : 10.1145/322123.322125