J. Araujo, V. Campos, F. Giroire, L. Sampaio, and R. Soares, On the hull number of some graph classes, Proceedings of the European Conference on Combinatorics, Graph Theory and Applications, 2011.
DOI : 10.1016/j.tcs.2012.12.035
URL : https://hal.archives-ouvertes.fr/inria-00635032

L. Babel and S. Olariu, On the isomorphism of graphs with few P4s, Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG '95, pp.24-36, 1995.
DOI : 10.1007/3-540-60618-1_63

L. Babel and S. Olariu, On the p-connectedness of graphs ??? a survey, Discrete Applied Mathematics, vol.95, issue.1-3, pp.11-33, 1999.
DOI : 10.1016/S0166-218X(99)00062-1

J. A. Bondy and U. S. Murty, Graph Theory. Graduate Texts in Mathematics, 2008.

G. B. Cagaanan, S. R. Canoy, and J. , On the hull sets and hull number of the cartesian product of graphs, Discrete Mathematics, vol.287, issue.1-3, pp.141-144, 2004.
DOI : 10.1016/j.disc.2004.06.014

M. Changat and J. Mathew, On triangle path convexity in graphs, Discrete Mathematics, vol.206, issue.1-3, pp.91-95, 1999.
DOI : 10.1016/S0012-365X(98)00394-X

M. Changat, H. M. Mulder, and G. Sierksma, Convexities related to path properties on graphs, Discrete Mathematics, vol.290, issue.2-3, pp.117-131, 2005.
DOI : 10.1016/j.disc.2003.07.014
URL : http://doi.org/10.1016/j.disc.2003.07.014

G. Chartrand, J. F. Fink, and P. Zhang, The hull number of an oriented graph, International Journal of Mathematics and Mathematical Sciences, vol.2003, issue.36, pp.2265-2275, 2003.
DOI : 10.1155/S0161171203210577

G. Chartrand, F. Harary, and P. Zhang, On the geodetic number of a graph, Networks, vol.4, issue.1, pp.1-6, 2002.
DOI : 10.1002/net.10007

G. Chartrand, C. E. Wall, and P. Zhang, The Convexity Number of a Graph, Graphs and Combinatorics, vol.18, issue.2, pp.209-217, 1007.
DOI : 10.1007/s003730200014

J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas, On the geodetic and the hull numbers in strong product graphs, Computers & Mathematics with Applications, vol.60, issue.11, pp.603020-3031, 2010.
DOI : 10.1016/j.camwa.2010.10.001

C. Mitre, J. G. Dourado, F. Kratochvíl, J. L. Protti, and . Szwarcfiter, On the computation of the hull number of a graph A Meeting in Celebration of Pavol Hell's 60th Birthday, Discrete Mathematics Combinatorics, vol.309, issue.18, pp.5668-5674, 2006.

C. Mitre, F. Dourado, D. Protti, J. L. Rautenbach, and . Szwarcfiter, On the hull number of trianglefree graphs, SIAM J. Discret. Math, vol.23, pp.2163-2172, 2010.

C. Mitre, F. Dourado, J. L. Protti, and . Szwarcfiter, Complexity results related to monophonic convexity, Traces from LAGOS'07 IV Latin American Algorithms, Graphs, and Optimization Symposium Puerto Varas -2007, pp.1268-1274, 2010.

G. Martin, S. B. Everett, and . Seidman, The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985.

M. Farber, E. Robert, and . Jamison, Convexity in Graphs and Hypergraphs, SIAM Journal on Algebraic Discrete Methods, vol.7, issue.3, pp.433-444, 1986.
DOI : 10.1137/0607049

A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Applied Mathematics, vol.148, issue.3, pp.256-262, 2005.
DOI : 10.1016/j.dam.2005.03.002

C. Hernando, T. Jiang, M. Mora, I. M. Pelayo, and C. Seara, On the Steiner, geodetic and hull numbers of graphs, British Combinatorial Conference, pp.139-154, 2005.
DOI : 10.1016/j.disc.2004.08.039

R. T. Rockafellar, Convex analysis. Princeton Mathematical Series, 1970.

A. Blanc, A. Anr, and I. , § Partially supported by CAPES/Brazil ¶ Partially supported by ANR Blanc AGAPE ANR-09-BLAN-0159, soares}@inria.fr - MASCOTTE Project, I3S (CNRS & UNS), p.38031, 2004.

B. Anand, M. Changat, S. Klav?ar, and I. Peterin, Convex Sets in Lexicographic Products of Graphs, Graphs and Combinatorics, vol.42, issue.1, pp.1-8, 2011.
DOI : 10.1007/s00373-011-1031-4

J. Araujo, V. Campos, F. Giroire, N. Nisse, L. Sampaio et al., On the hull number of some graph classes, Theoretical Computer Science, vol.475, 2011.
DOI : 10.1016/j.tcs.2012.12.035
URL : https://hal.archives-ouvertes.fr/inria-00635032

J. Araujo, V. Campos, F. Giroire, L. Sampaio, and R. Soares, On the hull number of some graph classes, The Sixth European Conference on Combinatorics, Graph Theory and Applications, pp.49-55, 2011.
DOI : 10.1016/j.tcs.2012.12.035
URL : https://hal.archives-ouvertes.fr/inria-00635032

G. Bacsó and Z. Tuza, Dominating cliques in P5-free graphs, Periodica Mathematica Hungarica, vol.3, issue.4, pp.303-308, 1990.
DOI : 10.1007/BF02352694

G. B. Cagaanan, S. R. Canoy, and J. , On the hull sets and hull number of the cartesian product of graphs, Discrete Mathematics, vol.287, issue.1-3, pp.141-144, 2004.
DOI : 10.1016/j.disc.2004.06.014

C. Mitre, F. Dourado, D. Protti, J. L. Rautenbach, and . Szwarcfiter, On the hull number of triangle-free graphs, SIAM J. Discret. Math, vol.23, pp.2163-2172, 2010.

G. Martin, S. B. Everett, and . Seidman, The hull number of a graph, Discrete Mathematics, vol.57, issue.3, pp.217-223, 1985.

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

R. Ganian, Using neighborhood diversity to solve hard problems, 2012.

M. Lampis, Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, vol.4, issue.3, pp.19-37, 2012.
DOI : 10.1007/s00453-011-9554-x

I. Peterin, The pre-hull number and lexicographic product, Discrete Mathematics, vol.312, issue.14, pp.2153-2157, 2010.
DOI : 10.1016/j.disc.2011.08.031
URL : http://dx.doi.org/10.1016/j.disc.2011.08.031

J. Araujo, C. Linhares, and . Sales, On the grundy number of graphs with few p 4 's, Discrete Applied Mathematics, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00639008

S. Arora and B. Barak, Computational Complexity: A Modern Approach, 2009.
DOI : 10.1017/CBO9780511804090

M. Asté, F. Havet, and C. Linhares-sales, Grundy number and products of graphs, Discrete Mathematics, vol.310, issue.9, pp.1482-1490, 2010.
DOI : 10.1016/j.disc.2009.09.020

L. Babel, T. Kloks, J. Kratochvíl, D. Kratsch, H. Müller et al., Efficient algorithms for graphs with few P4's, Discrete Mathematics, vol.235, issue.1-3, pp.29-51, 2001.
DOI : 10.1016/S0012-365X(00)00258-2

G. Bacsó and Z. Tuza, Dominating cliques in P5-free graphs, Periodica Mathematica Hungarica, vol.3, issue.4, pp.303-308, 1990.
DOI : 10.1007/BF02352694

R. Balakrishnan and T. Kavaskar, Color Chain of a Graph, Graphs and Combinatorics, vol.304, issue.4, pp.487-493, 2011.
DOI : 10.1007/s00373-010-0989-7

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

A. Beutelspacher and P. Hering, Minimal graphs for which the chromatic number equals the maximal degree, Ars Combinatoria, vol.18, pp.201-216, 1984.

T. Beyer, S. M. Hedetniemi, and S. T. Hedetniemi, A linear algorithm for the grundy number of a tree, Proceedings of the Thirteenth Southeastern Conference on Combinatorics, Graph Theory and Computing, pp.351-363, 1982.

M. Blidia, F. Maffray, and Z. Zemir, On <mml:math altimg="si3.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>b</mml:mi></mml:math>-colorings in regular graphs, Discrete Applied Mathematics, vol.157, issue.8, pp.1787-1793, 2009.
DOI : 10.1016/j.dam.2009.01.007

F. Bonomo, G. Durán, F. Maffray, J. Marenco, and M. Valencia-pabon, On the b-Coloring of Cographs and P 4-Sparse Graphs, Graphs and Combinatorics, vol.25, issue.2, pp.153-167, 2009.
DOI : 10.1007/s00373-008-0829-1
URL : https://hal.archives-ouvertes.fr/hal-00477747

O. V. Borodin and A. V. Kostochka, On an upper bound of a graph's chromatic number, depending on the graph's degree and density, Journal of Combinatorial Theory, Series B, vol.23, issue.2-3, pp.247-250, 1977.
DOI : 10.1016/0095-8956(77)90037-5

A. Brandstädt, Special graph classes -a survey, 1991.

R. L. Brooks, On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society, vol.37, issue.02, pp.194-197, 1941.
DOI : 10.1017/S030500410002168X

S. Cabello and M. Jakovac, On the b-chromatic number of regular graphs, Discrete Applied Mathematics, vol.159, issue.13, pp.1303-1310, 2011.
DOI : 10.1016/j.dam.2011.04.028

V. Campos, D. V. Farias, and A. Silva, b-Coloring graphs with large girth, Journal of the Brazilian Computer Society, vol.159, issue.3, pp.1-4, 2012.
DOI : 10.1007/s13173-012-0063-9

V. Campos, A. Gyárfás, F. Havet, C. L. Sales, and F. Maffray, New Bounds on the Grundy Number of Products of Graphs, Journal of Graph Theory, vol.306, issue.23, pp.78-88, 2012.
DOI : 10.1002/jgt.20633
URL : https://hal.archives-ouvertes.fr/inria-00470158

V. Campos, C. L. Sales, F. Maffray, and A. Silva, b-chromatic number of cacti, Electronic Notes in Discrete Mathematics, vol.35, issue.0, pp.281-286, 2009.
DOI : 10.1016/j.endm.2009.11.046
URL : https://hal.archives-ouvertes.fr/hal-00529162

V. Campos, C. L. Sales, A. Maia, and R. Sampaio, On b-colorings of graphs with few p4's, 8th French Combinatorial Conference, 2010.

V. Campos, C. L. Sales, K. Maia, N. Martins, and R. Sampaio, Restricted coloring problems on graphs with few, Electronic Notes in Discrete Mathematics, vol.37, pp.57-62, 2011.
DOI : 10.1016/j.endm.2011.05.011
URL : https://hal.archives-ouvertes.fr/hal-00643180

F. Chow and J. Hennessy, Register allocation by priority-based coloring, ACM SIGPLAN Notices, vol.19, issue.6, pp.222-232, 1984.
DOI : 10.1145/502949.502896

F. Chow and J. Hennessy, The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems, vol.12, issue.4, pp.501-536, 1990.
DOI : 10.1145/88616.88621

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. Chrobak and M. ´. Slusarek, On some packing problem related to dynamic storage allocation, RAIRO - Theoretical Informatics and Applications, vol.22, issue.4
DOI : 10.1051/ita/1988220404871

D. G. Corneil, H. Lerchs, and L. S. Burlingham, Complement reducible graphs, Discrete Applied Mathematics, vol.3, issue.3, pp.163-174, 1981.
DOI : 10.1016/0166-218X(81)90013-5

S. Corteel, M. Valencia-pabon, and J. C. Vera, On approximating the b-chromatic number, Discrete Applied Mathematics, vol.146, issue.1, pp.106-110, 2005.
DOI : 10.1016/j.dam.2004.09.006

P. David and . Dailey, Uniqueness of colorability and colorability of planar 4-regular graphs are np-complete, Discrete Mathematics, vol.30, issue.3, pp.289-293, 1980.

R. Diestel, Graph Theory, volume 173 of Graduate Texts in Mathematics, 2005.

R. G. Downey and M. R. Fellows, Parameterized Complexity. Monographs in Computer Science, 1999.
DOI : 10.1007/978-1-4612-0515-9
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.3797

J. E. Dunbar, S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, J. Knisely et al., Fall coloring of graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.33, pp.257-273, 2000.

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

T. Emden-weinert, S. Hougardy, and B. Kreuter, Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth, Combinatorics, Probability and Computing, vol.7, issue.4, pp.375-386, 1998.
DOI : 10.1017/S0963548398003678

P. Erd?-os, Graph theory and probability, Journal canadien de math??matiques, vol.11, issue.0, pp.34-38, 1959.
DOI : 10.4153/CJM-1959-003-9

P. Erdös, On the combinatorial problems which I would most like to see solved, Combinatorica, vol.70, issue.3???4, pp.25-42, 1979.
DOI : 10.1007/BF02579174

P. Erdös, W. R. Hare, S. T. Hedetniemi, and R. C. 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.1002/jgt.3190110205

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.53-64, 2003.
DOI : 10.1016/S0012-365X(03)00184-5

T. Faik, About the b-continuity of graphs, Workshop on Graphs and Combinatorial Optimization, pp.151-156, 2004.
DOI : 10.1016/j.endm.2004.03.030

T. Faik, La b-continuité des b-colorations: complexité, propriétés structurelles et algorithmiques, 2010.

B. Farzad, M. Molloy, and B. Reed, <mml:math altimg="si1.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:mo stretchy="false">(</mml:mo><mml:mi>??</mml:mi><mml:mo>-</mml:mo><mml:mi>k</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:math>-critical graphs, Journal of Combinatorial Theory, Series B, vol.93, issue.2, pp.173-185, 2005.
DOI : 10.1016/j.jctb.2004.09.006

D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, vol.15, issue.3, pp.835-855, 1965.
DOI : 10.2140/pjm.1965.15.835

D. Gaceb, V. Eglin, F. Lebourgeois, and H. Emptoz, Graph b-Coloring for Automatic Recognition of Documents, 2009 10th International Conference on Document Analysis and Recognition, pp.261-265, 2009.
DOI : 10.1109/ICDAR.2009.72
URL : https://hal.archives-ouvertes.fr/hal-01437695

]. T. Gallai, ¨ uber extreme punkt-und kantenmengen, pp.133-138, 1959.

A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE Transactions on Vehicular Technology, vol.35, issue.1, pp.8-14, 1986.
DOI : 10.1109/T-VT.1986.24063

M. R. Garey, D. S. Johnson, and L. J. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Computer Science, vol.1, issue.3, pp.237-267, 1976.
DOI : 10.1016/0304-3975(76)90059-1

V. Giakoumakis, P4-laden graphs: A new class of brittle graphs, Information Processing Letters, vol.60, issue.1, pp.29-36, 1996.
DOI : 10.1016/S0020-0190(96)00134-2

V. Giakoumakis, F. Russel, and H. Thuillier, On p 4 -tidy graphs, Discrete Mathematics and Theoretical Computer Science, vol.1, pp.17-41, 1997.
URL : https://hal.archives-ouvertes.fr/hal-00955688

J. L. Gonzalez-velarde and M. Laguna, Tabu search with simple ejection chains for coloring graphs, Annals of Operations Research, vol.117, issue.1/4, pp.165-174, 2002.
DOI : 10.1023/A:1021573507189

N. Goyal and S. Vishvanathan, Np-completeness of undirected grundy numbering and related problems. Unpublished Manuscript, 1997.

G. R. Grimmett and C. J. Mcdiarmid, On colouring random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, vol.5, issue.02, pp.313-324, 1975.
DOI : 10.1093/comjnl/10.1.85

M. Grotschel, L. Lovasz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization . Algorithms and Combinatorics, 1994.

P. M. Grundy, Mathematics and games, pp.6-8, 1939.

A. Gyárfás and J. Lehel, On-line and first fit colorings of graphs, Journal of Graph Theory, vol.29, issue.2, pp.217-227, 1988.
DOI : 10.1002/jgt.3190120212

P. Hall, On representatives of subsets, Journal London Mathematical Society, vol.10, issue.1, pp.26-30, 1935.

M. Halldórsson, Parallel and on-line graph coloring algorithms, Algorithms and Computation, pp.61-70, 1992.
DOI : 10.1007/3-540-56279-6_58

M. Halldórsson and M. Szegedy, Lower bounds for on-line graph coloring, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, SODA '92, pp.211-216, 1992.
DOI : 10.1016/0304-3975(94)90157-0

M. M. Halldórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, vol.45, issue.1, pp.19-23, 1993.
DOI : 10.1016/0020-0190(93)90246-6

J. Hamiez and J. Hao, Scatter Search for Graph Coloring, Selected Papers from the 5th European Conference on Artificial Evolution, pp.168-179, 2002.
DOI : 10.1007/3-540-46033-0_14

F. Havet and C. , Linhares Sales, and L. Sampaio. b-coloring of tight graphs, 2010.

F. Havet and C. , Linhares Sales, and L. Sampaio. b-coloring of tight graphs, Discrete Applied Mathematics, 2011.

F. Havet and L. Sampaio, On the Grundy and b-Chromatic Numbers of a Graph, Algorithmica, vol.306, issue.23, pp.1-15, 2011.
DOI : 10.1007/s00453-011-9604-4
URL : https://hal.archives-ouvertes.fr/hal-00905927

C. Hò, Perfect graphs, 1995.

C. T. Hoang and M. Kouider, On the b-dominating coloring of graphs, Discrete Applied Mathematics, vol.152, issue.1-3, pp.176-186, 2005.
DOI : 10.1016/j.dam.2005.04.001

C. T. Hò-ang and C. , On minimally b-imperfect graphs, Discrete Applied Mathematics, vol.157, issue.17, pp.3519-3530, 2009.
DOI : 10.1016/j.dam.2009.02.023

T. C. Hò-ang, F. Maffray, and M. Mechebbek, A characterization of b-perfect graphs, 2009.

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

J. E. Hopcroft and R. M. Karp, An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs, SIAM Journal on Computing, vol.2, issue.4, pp.225-231, 1973.
DOI : 10.1137/0202019

M. Hujter and Z. Tuza, Precoloring Extension III: Classes of Perfect Graphs, Combinatorics, Probability and Computing, vol.62, issue.01, pp.35-56, 1996.
DOI : 10.1016/0166-218X(94)90150-3

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

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.1007/s00373-010-0898-9

M. Jakovac and I. Peterin, On the b-chromatic number of strong, lexicographic, and direct product, Studia Scientiarum Mathematicarum Hungarica, 2009.

B. Jamison and S. Olariu, A New Class of Brittle Graphs, Studies in Applied Mathematics, vol.16, issue.1, pp.89-92, 1989.
DOI : 10.1002/sapm198981189

B. Jamison and S. Olariu, -Reducible Graphs-Class of Uniquely Tree-Representable Graphs, Studies in Applied Mathematics, vol.18, issue.1, pp.79-87, 1989.
DOI : 10.1002/sapm198981179
URL : https://hal.archives-ouvertes.fr/in2p3-00529133

B. Jamison and S. Olariu, On a unique tree representation for P4-extendible graphs, Discrete Applied Mathematics, vol.34, issue.1-3, pp.151-164, 1991.
DOI : 10.1016/0166-218X(91)90085-B

R. Javadi and B. Omoomi, On <mml:math altimg="si4.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>b</mml:mi></mml:math>-coloring of the Kneser graphs, Discrete Mathematics, vol.309, issue.13, pp.4399-4408, 2009.
DOI : 10.1016/j.disc.2009.01.017

R. Javadi and B. Omoomi, On b-coloring of cartesian product of graphs, Ars Combinatoria, 2010.

T. R. Jensen and B. Toft, Graph coloring problems. Wiley-Interscience Series in Discrete Mathematics and Optimization, 1995.

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

H. A. Kierstead, The Linearity of First-Fit Coloring of Interval Graphs, SIAM Journal on Discrete Mathematics, vol.1, issue.4, pp.526-530, 1988.
DOI : 10.1137/0401048

H. A. Kierstead and J. Qin, Coloring interval graphs with first-fit, Discrete Mathematics, vol.144, issue.1-3, pp.47-57, 1995.
DOI : 10.1016/0012-365X(94)00285-Q
URL : http://doi.org/10.1016/0012-365x(94)00285-q

D. König, GráfokGráfok´Gráfokés mátrixok Matematikaí es Fizikai Lapok, pp.116-119, 1931.

G. Kortsarz, A lower bound for approximating grundy number, Discrete Mathematics and Theoretical Computer Science, vol.9, issue.1, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00966515

M. Kouider, b-chromatic number of a graph, subgraphs and degrees, 2002.

M. Kouider and A. E. Sahili, About b-colouring of regular graphs, 2002.

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

M. Kouider and M. Mahéo, Some bounds for the b-chromatic number of a graph, Discrete Mathematics, vol.256, issue.1-2, pp.267-277, 2002.
DOI : 10.1016/S0012-365X(01)00469-1

D. Král, J. Kratochvíl, Z. Tuza, and G. J. Woeginger, Complexity of coloring graphs without forbidden induced subgraphs, Proceedings of the 27th International Workshop on Graph- Theoretic Concepts in Computer Science, pp.254-262, 2001.

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

L. Ku?era, The greedy coloring is a bad probabilistic algorithm, Journal of Algorithms, vol.12, issue.4, pp.674-684, 1991.
DOI : 10.1016/0196-6774(91)90040-6

W. T. Trotter, L. Lovász, and M. Saks, An online graph coloring algorithm with sublinear performance ratio, Discrete Mathematics, vol.75, pp.319-325, 1989.

W. Lin and G. Chang, b-coloring of tight graphs and the erdös-faber-lovász conjecture, Discrete Applied Mathematics

L. Lovász and M. D. Plummer, Matching Theory, 1986.
DOI : 10.1090/chel/367

L. Lovász, Three short proofs in graph theory, Journal of Combinatorial Theory, Series B, vol.19, issue.3, pp.111-113, 1975.
DOI : 10.1016/0095-8956(75)90089-1

C. Lucet, F. Mendes, and A. Moukrim, An exact method for graph coloring, Computers & Operations Research, vol.33, issue.8, pp.2189-2207, 2006.
DOI : 10.1016/j.cor.2005.01.008
URL : https://hal.archives-ouvertes.fr/hal-00783637

C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of the ACM, vol.41, issue.5, pp.960-981, 1994.
DOI : 10.1145/185675.306789

F. Maffray and A. Silva, b-colouring the Cartesian product of trees and some other graphs, Discrete Applied Mathematics, vol.161, issue.4-5, 2011.
DOI : 10.1016/j.dam.2011.06.019
URL : https://hal.archives-ouvertes.fr/hal-00977577

F. Maffray and A. Silva, b-colouring outerplanar graphs with large girth, Discrete Mathematics, issue.10, pp.3121796-1803, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00764263

D. Marx, Precoloring extension on chordal graphs In Graph Theory in Paris, Proceedings of a Conference in Memory of Claude Berge, pp.255-270, 2004.

D. Marx, Parameterized coloring problems on chordal graphs, Theoretical Computer Science, vol.351, issue.3, pp.407-424, 2006.
DOI : 10.1016/j.tcs.2005.10.008
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.9588

M. Molloy and B. Reed, Colouring graphs when the number of colours is nearly the maximum degree, Proceedings of the thirty-third annual ACM symposium on Theory of computing , STOC '01, pp.462-470, 2001.
DOI : 10.1145/380752.380840

M. Muchaand and P. Sankowski, Maximum matchings via gaussian elimination, Proc. 45st IEEE Symp. Foundations of Computer Science, pp.248-255, 2004.

N. Narayanaswamy and R. Babu, A Note on First-Fit Coloring of Interval Graphs, Order, vol.1, issue.4, pp.49-53, 2008.
DOI : 10.1007/s11083-008-9076-6

G. L. Nemhauser and L. A. Wolsey, Integer and combinatorial optimization, 1988.
DOI : 10.1002/9781118627372
URL : http://dx.doi.org/10.1016/s0898-1221(99)91259-2

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, 2006.
DOI : 10.1093/acprof:oso/9780198566076.001.0001

A. L. Rubin, P. Erdös, and H. Taylor, Choosability in graphs, Proceedings of the West Coast Conference on Combinatorics, Graph Theory and Computing, pp.125-157, 1979.

S. V. Pemmaraju, R. Raman, and K. Varadarajan, Buffer minimization using max-coloring, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '04, pp.562-571, 2004.

R. Raman, Chromatic scheduling, 2007.

B. Reed, ?, ?, and ?, Journal of Graph Theory, vol.27, issue.4, pp.177-212, 1998.
DOI : 10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K

B. Reed, A Strengthening of Brooks' Theorem, Journal of Combinatorial Theory, Series B, vol.76, issue.2, pp.136-149, 1999.
DOI : 10.1006/jctb.1998.1891

Y. Saad, Iterative Methods for Sparse Linear Systems, 1996.
DOI : 10.1137/1.9780898718003

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

A. Silva, The b-chromatic number of some tree-like graphs
URL : https://hal.archives-ouvertes.fr/tel-00544757

G. J. Simmons, On the ochromatic number of a graph, Congressus Numerantium, vol.40, pp.339-366, 1983.

J. A. 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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.152

Z. Tuza, Graph colorings with local constraints -- a survey, Discussiones Mathematicae Graph Theory, vol.17, issue.2, pp.161-228, 1997.
DOI : 10.7151/dmgt.1049

C. I. Velasquez, F. Bonomo, and I. Koch, On the <mml:math altimg="si3.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>b</mml:mi></mml:math>-coloring of <mml:math altimg="si4.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>4</mml:mn></mml:mrow></mml:msub></mml:math>-tidy graphs, Discrete Applied Mathematics, vol.159, issue.1, pp.60-68, 2011.
DOI : 10.1016/j.dam.2010.10.002

S. Vishwanathan, Randomized online graph coloring, Journal of Algorithms, vol.13, issue.4, pp.657-669, 1992.
DOI : 10.1016/0196-6774(92)90061-G

D. Werra, An introduction to timetabling, European Journal of Operational Research, vol.19, issue.2, pp.151-161, 1985.
DOI : 10.1016/0377-2217(85)90167-5

M. Zaker, The grundy chromatic number of the complement of bipartite graphs, Australasian Journal of Combinatorics, vol.31, pp.325-329, 2005.

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

D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing , STOC '06, 2007.
DOI : 10.1145/1132516.1132612