, S'il existe T une option de T qui est dans la même classe que S, alors le second joueur peut jouer cette option. Par induction, il laisse alors une P

, S'il existe T une option de S qui est dans la même classe que T , alors similairement

, Supposons finalement qu'aucun de ces deux cas ne se présente. Si G(S) = 3, on retombe dans le cas 2, et si G(S) = 0, alors on est dans le cas

. Bibliographie,

R. Adams, J. Dixon, J. Elder, J. Peabody, O. Vega et al., Combinatorial analysis of a subtraction game on graphs, International Journal of Combinatorics, 2016.

D. Adjiashvili, A. Baggio, and R. Zenklusen, Firefighting on trees beyond integrality gaps, Proceedings of the Twenty-Eighth Annual ACMSIAM Symposium on Discrete Algorithms, pp.2364-2383, 2017.

E. Anshelevich and D. Chakrabarty, Approximability of the firefighter problem-computing cuts over time, Algorithmica, vol.62, issue.1-2, pp.520-536, 2012.

D. Auger, I. Charon, O. Hudry, and A. Lobstein, Complexity results for identifying codes in planar graphs, International Transactions in Operational Research, vol.17, issue.6, pp.691-710, 2010.

G. Ausiello and L. Becchetti, On-line algorithms, V. Th. Paschos, editor, Paradigms of Combinatorial Optimization : Problems and New Approaches, vol.2, pp.473-509, 2010.
URL : https://hal.archives-ouvertes.fr/hal-00120329

C. Bazgan, M. Chopin, M. Cygan, M. R. Fellows, F. V. Fomin et al., Parameterized complexity of firefighting, Journal of Computer and System Sciences, vol.80, issue.7, pp.1285-1297, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01505557

C. Bazgan, M. Chopin, and B. Ries, The firefighter problem with more than one firefighter on trees, Discrete Applied Mathematics, vol.161, issue.78, pp.899-908, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01505574

. Elwyn-r-berlekamp, H. John, R. Conway, and . Guy, Winning Ways for Your Mathematical Plays, vol.3, 2009.

N. Bertrand, I. Charon, O. Hudry, and A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics, vol.25, issue.7, pp.969-987, 2004.

N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, and S. Thomassé, Identifying codes in hereditary classes of graphs and vc-dimension, SIAM Journal on Discrete Mathematics, vol.29, issue.4, pp.2047-2064, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01038012

D. Boutin, V. H. Goliber, and M. Pelto, Identifying codes on directed de bruijn graphs, 2014.

L. Cai, E. Verbin, and L. Yang, Firefighting on trees : (1-1/e)approximation, fixed parameter tractability and a subexponential algorithm, Algorithms and Computation, 19th International Symposium, pp.258-269, 2008.

I. Charon, S. Gravier, O. Hudry, and A. Lobstein, Michel Mollard, and Julien Moncel. A linear algorithm for minimum 1-identifying codes in oriented trees, Discrete Applied Mathematics, vol.154, issue.8, pp.1246-1253, 2006.

I. Charon, O. Hudry, and A. Lobstein, Identifying and locatingdominating codes : Np-completeness results for directed graphs, IEEE Transactions on Information Theory, vol.48, issue.8, pp.2192-2200, 2002.

I. Charon, O. Hudry, and A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is np-hard, Theoretical Computer Science, vol.290, issue.3, pp.2109-2120, 2003.

J. Chlebíková and M. Chopin, The firefighter problem : Further steps in understanding its complexity, Theoretical Compututer Science, vol.676, pp.42-51, 2017.

P. Coupechoux, Extension of universal cycles for globally identifying colorings of cycles, Discrete Mathematics, vol.340, issue.7, pp.1456-1466, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01704385

M. Develin and S. G. Hartke, Fire containment in grids of dimension three and higher, Discrete Applied Mathematics, vol.155, issue.17, pp.2257-2268, 2007.

É. Duchêne, S. Gravier, and M. Mhalla, Scoring octal games on trees, 2016.

D. Dyer, E. Martínez-pedroza, and B. Thorne, The coarse geometry of hartnell's firefighter problem on infinite graphs, Discrete Mathematics, vol.340, issue.5, pp.935-950, 2017.

N. Ohad, R. Feldheim, and . Hod, 3/2 firefighters are not enough, Discrete Applied Mathematics, vol.161, issue.1-2, pp.301-306, 2013.

S. Finbow, A. King, G. Macgillivray, and R. Rizzi, The firefighter problem for graphs of maximum degree three, Discrete Mathematics, vol.307, issue.16, pp.2094-2105, 2007.

S. Finbow and G. Macgillivray, The firefighter problem : a survey of results, directions and questions, Australasian Journal of Combinatorics, vol.43, issue.6, pp.57-77, 2009.

P. Fogarty, Catching the Fire on Grids, 2003.

V. Fedor, P. Fomin, E. J. Heggernes, and . Van-leeuwen, The firefighter problem on graph classes, Theoretical Compututer Science, vol.613, issue.C, pp.38-50, 2016.

F. Foucaud, The complexity of the identifying code problem in restricted graph classes, International Workshop on Combinatorial Algorithms, pp.150-163, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00960564

F. Foucaud, I. Honkala, and T. Laihonen, Aline Parreau, and Guillem Perarnau. Locally identifying colourings for graphs with given maximum degree, Discrete Mathematics, vol.312, pp.1832-1837, 2012.

F. Foucaud, R. Naserasr, and A. Parreau, Characterizing extremal digraphs for identifying codes and extremal cases of bondy's theorem on induced subsets, Graphs and Combinatorics, vol.29, issue.3, pp.463-473, 2013.

S. Gravier and J. Moncel, Construction of codes identifying sets of vertices. the electronic journal of combinatorics, vol.12, p.13, 2005.
URL : https://hal.archives-ouvertes.fr/hal-00360014

G. Stephen and . Hartke, Attempting to narrow the integrality gap for the firefighter problem on trees, Discrete Methods in Epidemiology, pp.225-232, 2004.

B. Hartnell and Q. Li, Firefighting on trees : How bad is the greedy algorithm ? Congressus Numerantium, pp.187-192, 2000.

, Berth Hartnell. Firefighter ! an application of domination. 1995. presented at the 10th Conference on Numerical Mathematics and Computing

I. Honkala and T. Laihonen, On the identification of sets of points in the square lattice, Discrete and Computational Geometry, vol.29, issue.1, pp.139-152, 2003.

O. Hudry, Complexity of voting procedures, Encyclopedia of Complexity and Systems Science, pp.9942-9965, 2009.

Y. Iwaikawa, N. Kamiyama, and T. Matsui, Improved approximation algorithms for firefighter problem on trees, IEICE Transactions on Information and Systems, vol.94, issue.2, pp.196-199, 2011.

B. W. Jackson, Universal cycles of k-subsets and k-permutations, Discrete Mathematics, vol.117, pp.141-150, 1993.
DOI : 10.1016/0012-365x(93)90330-v
URL : https://doi.org/10.1016/0012-365x(93)90330-v

G. Mark, K. Karpovsky, L. B. Chakrabarty, and . Levitin, On a new class of codes for identifying properties in graphs, IEEE transactions on information theory, vol.44, 1998.

K. Mark-g-karpovsky, L. B. Chakrabarty, and . Levitin, On a new class of codes for identifying vertices in graphs, IEEE Transactions on Information Theory, vol.44, issue.2, pp.599-611, 1998.

G. Macgillivray and P. Wang, On the firefighter problem, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.47, pp.83-96, 2003.

M. Messinger, Average firefighting on infinite grids. The Australasian, Journal of Combinatorics, vol.41, pp.15-28, 2008.

J. W. Moon, Topics on tournaments. Holt, Rinehart and Winston, 1968.

A. Parreau, Problèmes d'identification dans les graphes, 2012.

V. Sergey and . Savchenko, On the number of 7-cycles in regular n-tournaments. Discrete Mathematics, vol.340, pp.264-285, 2017.

J. Thomas and . Schaefer, On the complexity of some two-person perfect-information games, Journal of Computer and System Sciences, vol.16, issue.2, pp.185-225, 1978.

T. Schwartz, Cyclic tournaments and cooperative majority voting : A solution, Social Choice and Welfare, vol.7, issue.1, pp.19-29, 1990.
DOI : 10.1007/bf01832917

A. Semri and H. Touati, Optimal identifying codes in oriented paths and circuits, Proceedings of the 2013 International Conference on Applied Mathematics and Computational Methods, pp.123-128, 2013.

R. Sprague, Über mathematische kampfspiele, Tohoku Mathematical Journal, First Series, vol.41, pp.438-444, 1935.

P. Wang and S. A. Moeller, Fire control on graphs, Journal of Combinatorial Mathematics and Combinatorial Computing, vol.41, pp.19-34, 2002.

K. A. and W. , Identifying codes and domination in the product of graphs, 2014.