G. Entrée:-un-graphe-cubique and E. , Un ensemble S ? E des arêtes déjà colorées, Une fonction c : S ? {1

?. Tant-que and |. Tel-que, S| = 2 alors : Soit xy = E(x)\S l'arête adjacente à x pas encore colorée, Soient {?, ?} = {c(e)|e ? S ? E(x)} et ? = {1, 2, 3}\{?, ?}, Si ? ? {c(e)|e ? S ? E(y)}, alors STOP ; Sinon, c(xy) ? ?

H. Si-le-graphe and . G\s-contient-un-composant-f-qui-n, est pas un cycle, alors : Choisir un sommet x ? V (F ) tel que d F (z) < 3, Choisir une arête xy ? E(x)\S, Soit {?, ?} = {1, (e)|e ? E(x) ? S}, Soit res = ? un ensemble de fonctions de E(G) ? {1, 2, 3}, Si ? / ? {c(e)|e ? E(y) ? S}, p.3

. Si, H. Dans, and . G\s-un-composant-f-qui-est-un-cycle, pour tout x ? V (F ) alors c(E(x) ? S) = ?, alors : Soit {?, ?} = {1, 3}\?, et soit e ? E(F ), Soit res = ? un ensemble de fonctions de E(G) ? {1, p.3

. Bibliographie, Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics, vol.135, pp.3-16, 2004.

G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. L. Hammer et al., Consensus algorithms for the generation of all maximal bicliques, Discrete Applied Mathematics, vol.145, issue.1, pp.145-156, 2004.
DOI : 10.1016/j.dam.2003.09.004

J. Amilhastre, M. Vilarem, and P. Janssen, Complexity of minimum biclique cover and minimum biclique decomposition for bipartite domino-free graphs, Discrete Applied Mathematics, vol.86, issue.2-3, pp.125-144, 1998.
DOI : 10.1016/S0166-218X(98)00039-0

E. Balas and C. S. Yu, On graphs with polynomially solvable maximum-weight clique problem, Networks, vol.10, issue.2, pp.247-253, 1989.
DOI : 10.1002/net.3230190206

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

R. Bellman, Dynamic programming and stochastic control processes, Information and Control, vol.1, issue.3, pp.228-239, 1958.
DOI : 10.1016/S0019-9958(58)80003-0

A. A. Bertossi, Dominating sets for split and bipartite graphs, Information Processing Letters, vol.19, issue.1, pp.37-40, 1984.
DOI : 10.1016/0020-0190(84)90126-1

S. Bessy and F. Havet, Enumerating the edge-colourings and total colourings of a regular graph, Journal of Combinatorial Optimization, vol.78, issue.3, pp.1-13
DOI : 10.1016/0012-365X(89)90187-8

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

D. Binkele-raible, H. Fernau, S. Gaspers, and M. Liedloff, Exact exponential-time algorithms for finding bicliques, Information Processing Letters, vol.111, issue.2, pp.64-67, 2010.
DOI : 10.1016/j.ipl.2010.10.020

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

A. Björklund and T. Husfeldt, Inclusion--Exclusion Algorithms for Counting Set Partitions, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.575-582, 2006.
DOI : 10.1109/FOCS.2006.41

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

J. R. Blair and B. W. Peyton, An introduction to chordal graphs and clique trees, Graph Theory and Sparse Matrix Computations, pp.56-57, 1998.

N. Bourgeois, B. Escoffier, V. T. Paschos, and J. M. Van-rooij, A Bottom-Up Method and Fast Algorithms for max independent set, SWAT, pp.62-73, 2010.
DOI : 10.1007/978-3-642-13731-0_7

A. Brandstädt and D. Kratsch, On domination problems for permutation and other graphs, Theoretical Computer Science, vol.54, issue.2-3, pp.181-198, 1987.
DOI : 10.1016/0304-3975(87)90128-9

A. Brandstädt, V. Le, and J. Spinrad, Graph Classes : A Survey, Siam Monographs on Discrete Mathematics and Applications, 1999.
DOI : 10.1137/1.9780898719796

B. Bui-xuan, J. A. Telle, and M. Vatshelle, Feedback Vertex Set on Graphs of Low Cliquewidth, IWOCA, pp.113-124, 2009.
DOI : 10.1007/978-3-642-10217-2_14

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

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

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction To Algorithms, 2001.

D. Corneil and Y. Perl, Clustering and domination in perfect graphs, Discrete Applied Mathematics, vol.9, issue.1, pp.27-39, 1984.
DOI : 10.1016/0166-218X(84)90088-X

D. G. Corneil and J. Fonlupt, The complexity of generalized clique covering, Discrete Applied Mathematics, vol.22, issue.2, pp.109-118, 1989.
DOI : 10.1016/0166-218X(88)90086-8

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

J. Couturier, P. A. Golovach, D. Kratsch, and D. Paulusma, List coloring in the absence of a linear forest On the parameterized complexity of coloring graphs in the absence of a linear forest, WG, pp.119-130, 2011.

J. Couturier, P. Heggernes, P. Van-'t-hof, and D. Kratsch, Minimal dominating sets in graph classes : Combinatorial bounds and enumeration, SOFSEM, 2012, pp.202-213

J. Couturier, P. Heggernes, P. Van-'t-hof, and Y. Villanger, Maximum Number of Minimal Feedback Vertex Sets in Chordal Graphs and Cographs, COCOON, pp.2012-133
DOI : 10.1007/978-3-642-32241-9_12

J. Couturier and D. Kratsch, Bicolored independent sets and bicliques, CTW, pp.130-133, 2011.
DOI : 10.1016/j.ipl.2012.01.010

M. Dawande, P. Keskinocak, J. M. Swaminathan, and S. Tayur, On Bipartite and Multipartite Clique Problems, Journal of Algorithms, vol.41, issue.2, pp.388-403, 2001.
DOI : 10.1006/jagm.2001.1199

V. M. Dias, C. M. De-figueiredo, and J. L. Szwarcfiter, Generating bicliques of a graph in lexicographic order, Theoretical Computer Science, vol.337, issue.1-3, pp.240-248, 2005.
DOI : 10.1016/j.tcs.2005.01.014

T. Eiter and G. Gottlob, Hypergraph Transversal Computation and Related Problems in Logic and AI, Lecture Notes in Computer Science, vol.2424, pp.549-564, 2002.
DOI : 10.1007/3-540-45757-7_53

D. Eppstein, Small Maximal Independent Sets and Faster Exact Graph Coloring, Journal of Graph Algorithms and Applications, vol.7, issue.2, pp.131-140, 2003.
DOI : 10.7155/jgaa.00064

URL : http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf

R. J. Faudree, E. Flandrin, and Z. Ryjácek, Claw-free graphs ??? A survey, Discrete Mathematics, vol.164, issue.1-3, pp.87-147, 1997.
DOI : 10.1016/S0012-365X(96)00045-3

H. Fernau, S. Gaspers, D. Kratsch, M. Liedloff, and D. Raible, Exact exponential-time algorithms for finding bicliques in a graph, CTW, pp.205-209, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00943037

J. Fiala, T. Kloks, and J. Kratochvíl, Fixed-parameter complexity of ??-labelings, Discrete Applied Mathematics, vol.113, issue.1, pp.59-72, 2001.
DOI : 10.1016/S0166-218X(00)00387-5

J. Flum and M. Grohe, Parameterized Complexity Theory, Theoretical Computer Science, 2006.

F. Fomin and D. Kratsch, Exact Exponential Algorithms, Texts in Theoretical Computer Science. an EATCS Series, 2010.

F. V. Fomin, S. Gaspers, A. V. Pyatkin, and I. Razgon, On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms, Algorithmica, vol.117, issue.2, pp.52-293, 2008.
DOI : 10.1007/3-540-36136-7_22

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

F. V. Fomin, S. Gaspers, S. Saurabh, and A. A. Stepanov, On Two Techniques of Combining Branching and Treewidth, Algorithmica, vol.348, issue.2, pp.54-181, 2009.
DOI : 10.1007/978-3-540-28639-4_25

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

F. V. 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. 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, 2008.
DOI : 10.1145/1435375.1435384

F. V. Fomin and A. A. Stepanov, Counting Minimum Weighted Dominating Sets, COCOON, pp.165-175, 2007.
DOI : 10.1007/978-3-540-73545-8_18

F. V. Fomin and Y. Villanger, Finding induced subgraphs via minimal triangulations, STACS, pp.383-394, 2010.
DOI : 10.1137/140964801

URL : https://hal.archives-ouvertes.fr/inria-00455360

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

S. Gaspers, D. Kratsch, and M. Liedloff, On independent sets and bicliques in graphs, WG, pp.171-182, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00460773

S. Gaspers and M. Mnich, Feedback vertex sets in tournaments, ESA (1), pp.267-277, 2010.

P. A. Golovach, D. Kratsch, and J. Couturier, Colorings with Few Colors: Counting, Enumeration and Combinatorial Bounds, WG, pp.39-50, 2010.
DOI : 10.1006/jagm.1996.0061

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

M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals of Discrete Mathematics, vol.57, 2004.

T. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs, Monographs and Textbooks in Pure and Applied Mathematics, 1998.

M. Held and R. Karp, A Dynamic Programming Approach to Sequencing Problems, Journal of the Society for Industrial and Applied Mathematics, vol.10, issue.1, pp.196-210, 1962.
DOI : 10.1137/0110015

P. Hell and J. Nesetril, On the complexity of H-coloring, Journal of Combinatorial Theory, Series B, vol.48, issue.1, pp.92-110, 1990.
DOI : 10.1016/0095-8956(90)90132-J

I. Holyer, The NP-Completeness of Edge-Coloring, SIAM Journal on Computing, vol.10, issue.4, pp.718-720, 1981.
DOI : 10.1137/0210055

Y. Iwata, A Faster Algorithm for Dominating Set Analyzed by the Potential Method, IPEC, pp.41-54, 2011.
DOI : 10.1016/j.jalgor.2004.01.001

D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, On generating all maximal independent sets, Information Processing Letters, vol.27, issue.3, pp.119-123, 1988.
DOI : 10.1016/0020-0190(88)90065-8

M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine, Enumeration of minimal dominating sets and variants, in FCT, pp.298-309, 2011.

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.

J. Kleinberg and É. Tardos, Algorithm Design, 2006.

M. Koivisto, An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion, 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp.583-590, 2006.
DOI : 10.1109/FOCS.2006.11

L. Kowalik, Improved edge-coloring with three colors, Theoretical Computer Science, vol.410, issue.38-40, pp.3733-3742, 2009.
DOI : 10.1016/j.tcs.2009.05.005

J. Kratochvíl, D. Kratsch, and M. Liedloff, Exact Algorithms for L(2,1)-Labeling of Graphs, MFCS, pp.513-524, 2007.
DOI : 10.1007/978-3-540-74456-6_46

D. Kratsch, Domination and total domination on asteroidal triple-free graphs, Discrete Applied Mathematics, vol.99, issue.1-3, pp.111-123, 2000.
DOI : 10.1016/S0166-218X(99)00128-6

D. Kratsch and L. Stewart, Domination on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.3, pp.400-417, 1993.
DOI : 10.1137/0406032

K. Kutzkov, An exact exponential time algorithm for counting bipartite cliques, Information Processing Letters, vol.112, issue.13, pp.535-539, 2012.
DOI : 10.1016/j.ipl.2012.04.001

E. Lawler, Combinatorial optimization : networks and matroids, 1976.

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

M. Liedloff, Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : Domination, variantes et généralisations, 2007.

P. J. Looges and S. Olariu, Optimal greedy algorithms for indifference graphs, Computers & Mathematics with Applications, vol.25, issue.7, pp.15-25, 1993.
DOI : 10.1016/0898-1221(93)90308-I

V. V. Lozin and R. Mosca, Independent sets in extensions of <mml:math altimg="si4.gif" 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:mn>2</mml:mn><mml:msub><mml:mrow><mml:mi>K</mml:mi></mml:mrow><mml:mrow><mml:mn>2</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs, Discrete Applied Mathematics, vol.146, issue.1, pp.74-80, 2005.
DOI : 10.1016/j.dam.2004.07.006

K. Makino and T. Uno, New Algorithms for Enumerating All Maximal Cliques, SWAT, pp.260-272, 2004.
DOI : 10.1007/978-3-540-27810-8_23

R. M. Mcconnell, Linear-time recognition of circular-arc graphs, pp.37-93, 2003.

A. A. Mcrae, Generalizing np-completeness proofs for bipartite graphs and chordal graphs, Department of Mathematical science, Clemson university, Ph.D. Dissertation, 1994.

G. J. Minty, On maximal independent sets of vertices in claw-free graphs, Journal of Combinatorial Theory, Series B, vol.28, issue.3, pp.284-304, 1980.
DOI : 10.1016/0095-8956(80)90074-X

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 P. Raghavan, Randomized Algorithms, 1995.

J. Nederlof, Fast Polynomial-Space Algorithms Using M??bius Inversion: Improving on Steiner Tree and Related Problems, ICALP (1), pp.713-725, 2009.
DOI : 10.1007/978-3-540-28639-4_25

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

Y. Okamoto, R. Uehara, and T. Uno, Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes, WG, pp.296-307, 2009.
DOI : 10.1007/978-3-642-11409-0_26

Y. Okamoto, T. Uno, and R. Uehara, Counting the number of independent sets in chordal graphs, Journal of Discrete Algorithms, vol.6, issue.2, pp.229-242, 2008.
DOI : 10.1016/j.jda.2006.07.006

S. Olariu, Paw-free graphs, Information Processing Letters, vol.28, issue.1, pp.53-54, 1988.
DOI : 10.1016/0020-0190(88)90143-3

C. Papadimitriou, Computational complexity, 1994.

R. Peeters, The maximum edge biclique problem is NP-complete, Discrete Applied Mathematics, vol.131, issue.3, pp.651-654, 2003.
DOI : 10.1016/S0166-218X(03)00333-0

J. Pfaff, R. Laskar, and S. Hedetniemi, Np-completeness of total and connected domination, and irredundance for bipartite graphs, Department of Mathematical science, Clemson university, 1983.

B. Randerath and I. Schiermeyer, On maximum independent sets in <mml:math altimg="si1.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:msub><mml:mrow><mml:mi>P</mml:mi></mml:mrow><mml:mrow><mml:mn>5</mml:mn></mml:mrow></mml:msub></mml:math>-free graphs, Discrete Applied Mathematics, vol.158, issue.9, pp.1041-1044, 2010.
DOI : 10.1016/j.dam.2010.01.007

R. C. Laskar and J. Pfaff, Domination and irredundance in split graphs, Department of Mathematical science, Clemson university, 1983.

F. S. Roberts, Indifference graphs, Proof techniques in graph theory, pp.139-146, 1969.

A. Sánchez-arroyo, Determining the total colouring number is np-hard, Discrete Mathematics, vol.78, issue.3, pp.315-319, 1989.
DOI : 10.1016/0012-365X(89)90187-8

B. Schwikowski and E. Speckenmeyer, On enumerating all minimal solutions of feedback problems, Discrete Applied Mathematics, vol.117, issue.1-3, pp.253-265, 2002.
DOI : 10.1016/S0166-218X(00)00339-5

L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science, vol.8, issue.2, pp.189-201, 1979.
DOI : 10.1016/0304-3975(79)90044-6

J. M. Van-rooij, Exact Exponential-Time Algorithms for Domination Problems in Graphs

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

V. G. Vizing, On an estimate of the chromatic class of a p-graph, 1964.

D. West, Introduction to graph theory, 2001.

D. Williamson and D. Shmoys, The Design of Approximation Algorithms, 2011.
DOI : 10.1017/CBO9780511921735

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

E. Wolk, The comparability graph of a tree, Proceedings of the American Mathematical Society, pp.189-175, 1962.
DOI : 10.1090/S0002-9939-1962-0172273-0

M. Yannakakis, Node-and edge-deletion NP-complete problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.253-264, 1978.
DOI : 10.1145/800133.804355

M. Yannakakis and F. Gavril, Edge Dominating Sets in Graphs, Society for Industrial and Applied Mathematic, pp.364-372, 1980.
DOI : 10.1137/0138030