J. Akiyama, H. Era, S. V. Gervacio, and M. Watanabe, Path chromatic numbers of graphs, Journal of Graph Theory, vol.13, issue.5, pp.571-573, 1989.
DOI : 10.1002/jgt.3190130506

M. O. Albertson and D. M. Berman, The acyclic chromatic number, Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp.51-69, 1976.

N. Alon, Transversal numbers of uniform hypergraphs, Graphs and Combinatorics, vol.14, issue.1, pp.1-4, 1990.
DOI : 10.1007/BF01787474

S. Bau, L. W. Beineke, and R. C. Vandell, Decycling snakes, Congr. Numer, vol.134, pp.79-87, 1998.

R. Boliac, K. Cameron, and V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Comb, pp.241-253, 2004.

Y. Caro, New Results on the Independence Number, 1979.

T. Cormen, C. E. Leiserson, and R. L. , Rivest: Introduction to algorithms, 1990.

B. Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Information and Computation, vol.85, issue.1, pp.12-75, 1990.
DOI : 10.1016/0890-5401(90)90043-H
URL : https://hal.archives-ouvertes.fr/hal-00353765

L. J. Cowen and C. E. Jesurum, Coloring with defects, DIMACS Technical Report, pp.95-120, 1995.

I. Dinur and S. Safra, On the hardness of approximating vertex cover, Annals of Mathematics, vol.162, issue.1, pp.439-485, 2005.
DOI : 10.4007/annals.2005.162.439

P. Festa, P. M. Pardolos, and M. G. Resende, Feedback set problems, AT&T Labs, Encyclopedia of Optimization, 1999.
DOI : 10.1007/0-306-48332-7_135

M. Frick and F. Bullock, Detour chromatic number, Discuss. Math. Graph Theory, vol.21, pp.283-291, 2001.

D. Gollmann, Protocol Analysis for Concrete Environments, EUROCAST 2005, pp.365-372, 2005.
DOI : 10.1007/11556985_47

F. Göring, J. Harant, and D. , Rautenbach and I. Schiermeyer, On Findependence in graphs, Discussiones Mathematicae Graph Theory, vol.29, pp.2-377, 2009.

J. Harant, M. A. Henning, D. Rautenbach, and I. Schiermeyer, Independence Number in Graphs of Maximum Degree Three, Discrete Math, pp.5829-5833, 2008.

J. Harant and I. Schiermeyer, On the independence number of a graph in terms of order and size, Discrete Math, pp.131-138, 2001.

C. C. Heckman, On the Tightness of the 5/14 Independence Ratio, Discrete Math, pp.3169-3179, 2008.

C. C. Heckman and R. Thomas, A New Proof of the Independence Ratio of Triangle-Free Cubic Graphs, Discrete Math, pp.233-237, 2001.

Y. Jinjiang, Computational complexity of (2,2) path chromatic number problem, Applied Mathematics-A Journal of Chinese Universities, vol.21, issue.4, pp.83-88, 1995.
DOI : 10.1007/BF02663898

G. Johns and F. Saba, On the Path-Chromatic Number of a Graph, Annals of the New York Academy of Sciences, vol.11, issue.1 Graph Theory, pp.275-280, 1989.
DOI : 10.1111/j.1749-6632.1989.tb16408.x

R. M. Karp, Reducibility among combinatorial problems, Complexity of computer computations, pp.85-104, 1972.

L. Lovász, On decompositions of graphs, Studia Sci. Math Hungar, vol.1, pp.237-238, 1966.

C. Löwenstein, A. S. Pedersen, D. Rautenbach, and F. Regen, Independence, odd girth, and average degree, Journal of Graph Theory, vol.99, issue.2, 20518.
DOI : 10.1002/jgt.20518

C. M. Mynhardt and I. Broere, Generalized colorings of graphs, Graph theory with applications to algorithms and computer science, pp.583-594, 1985.

M. Novotn´ynovotn´y, Design and Analysis of a Generalized Canvas Protocol, Proceedings of WISTP 2010, pp.106-121, 2010.

M. Novotn´ynovotn´y, Formal analysis of security protocols for wireless sensor networks, Tatra Mt, Math. Publ, vol.47, pp.81-97, 2010.

S. Thomassé and A. Yeo, Total domination of graphs and small transversals of hypergraphs, Combinatorica, vol.25, issue.4, pp.473-487, 2007.
DOI : 10.1007/s00493-007-2020-3

H. Vogt, Integrity preservation for communication in sensor networks Institute for Pervasive Computing, ETH Zürich, 2004.

V. K. Wei, A Lower Bound on the Stability Number of a Simple Graph, 1981.

D. B. West, Introduction to graph theory, 1996.

R. Williams, Finding paths of length k in time, Information Processing Letters, vol.109, issue.6, pp.315-318, 2009.
DOI : 10.1016/j.ipl.2008.11.004

M. Yannakakis, Node-Deletion Problems on Bipartite Graphs, SIAM Journal on Computing, vol.10, issue.2, pp.310-327, 1981.
DOI : 10.1137/0210022