. Proof, Let u, v and w be three distinct vertices of X and let z be a common neighbor of these three vertices, since it would imply that either v or w belongs to V (C u ). Thus, there exist two distinct vertices u 1

B. Moreover and . Property, 4 ) are two pairs of adjacent vertices In this case, we remove U from X and replace it by {u 13 , u 14 , u 24 }, contradicting the minimality of X. (B3): Suppose, without loss of generality, that u 12 and u 13 exist and are adjacent. Let u ? and u ?? be two existing vertices among {u 14 , u 23 , u 24 , u 34 } such that the three vertices u ? , u ?? and u 13 have no common neighbor. In this case, we remove U from X and replace it by {u ? , u ?? , u 13 }, contradicting the minimality of X. There exist three configurations depending on which are the two adjacent vertices from U . However, for the three possibilities, it is trivial to check that if we remove U from X and replace it by {u ? , u ?? , u 13 } we obtain an odd-cut set, B4): Suppose, without loss of generality, that u 1 and u 2 are adjacent. We can remark that, by Property (B1), no vertex of {u 13 Consequently, every odd cycle C with u 1 ? V (C) contains also another vertex of X

X. \. Hence and . {u, } is an odd-cut set, contradicting the minimality of X. By symmetry, the same goes for u 14 , u 23 and u 24 . (B5): Suppose that the vertex u 12 satisfies |B 2 (u 12 ) ? X| > 3. We can remark that if u 13 satisfied also |B 2 (u 13 ) ? X| > 3, then, as for Property (B4), X \ {u 1 } would be an oddcut set

J. L. Yebra, Suppose that the vertices of two pairs among {(u 12 u 23 )} have a common neighbor and that these two pairs are (u 12 Notice that (X \ U ) ?{u ? 12 , u 14 , u 23 } is also an odd-cut set, contradicting the minimality of X. Note that in this case, there is an even cycle containing each vertex of U that does not contain vertices of (X \ U ) ? {u ? 12 , u 14 , u 23 }. Now suppose that X is an odd-cut set in G of minimum cardinality minimizing |E(G X )|. We consider two types of induced K 4 in G X . The first type is a K 4 such that U is an independent set in G and that both (u 12 , u 34 ) and (u 14 , u 23 ) are pairs of vertices with no common neighbor. The second type is a K 4 such that u 1 and u 2 are adjacent in G Some large graphs with given degree and diameter, Consequently, we can remove {u 1 } from X and replace it by {u 13 }, contradicting the minimality of |E(G X )|. By symmetry 34 ) and (u 13 , u 24 ), i.e. N (u 12 )?N (u 34 ) = ? and N (u 13 ) ? N (u 24 ) = ? (other pairs can be treated similarly By Properties (B2), (B3) and (B6), every induced K 4 in G X is isomorphic to an induced K 4 of the first or second type. We construct Y by replacing U by {u 12, pp.34219-224, 1986.

O. V. Borodin and A. O. , 2-Distance 4-coloring of planar subcubic graphs, Journal of Applied and Industrial Mathematics, vol.5, issue.4, pp.535-541, 2011.
DOI : 10.1134/S1990478911040089

B. Bre?ar, S. Klav?ar, and D. F. , On the packing chromatic number of Cartesian products, hexagonal lattice, and trees, Discrete Applied Mathematics, vol.155, issue.17, pp.2303-2311, 2007.
DOI : 10.1016/j.dam.2007.06.008

B. Bre?ar, S. Klav?ar, and D. F. , Packing Chromatic Number of Base-3 Sierpi´nskiSierpi´nski Graphs. Graphs and Combinatorics, Available, vol.online, pp.1-15, 2015.

D. W. Cranston and S. Kim, List-coloring the square of a subcubic graph, Journal of Graph Theory, vol.17, issue.1, pp.65-87, 2008.
DOI : 10.1002/jgt.20273

J. Ekstein, J. Fiala, P. Holub, and B. Lidick´ylidick´y, The packing chromatic number of the square lattice is at least 12, 2010.

J. Fiala and P. A. Golovach, Complexity of the packing coloring problem for trees, Discrete Applied Mathematics, vol.158, issue.7, pp.771-778, 2010.
DOI : 10.1016/j.dam.2008.09.001

J. Fiala, S. Klav?ar, and B. Lidick´ylidick´y, The packing chromatic number of infinite product graphs, European Journal of Combinatorics, vol.30, issue.5, pp.1101-1113, 2009.
DOI : 10.1016/j.ejc.2008.09.014

A. S. Finbow and D. F. , On the packing chromatic number of some lattices, Discrete Applied Mathematics, vol.158, issue.12, pp.1224-1228, 2010.
DOI : 10.1016/j.dam.2009.06.001

N. Gastineau, Dichotomies properties on computational complexity of <mml:math altimg="si26.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" xmlns:sa="http://www.elsevier.com/xml/common/struct-aff/dtd"><mml:mi>S</mml:mi></mml:math>-packing coloring problems, Discrete Mathematics, vol.338, issue.6, pp.1029-1041, 2015.
DOI : 10.1016/j.disc.2015.01.028

N. Gastineau, H. Kheddouci, and O. Togni, Subdivision into i-packings and S-packing chromatic number of some lattices, Ars Math. Cont, vol.9, pp.331-354, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01157901

W. Goddard, S. M. Hedetniemi, S. T. Hedetniemi, J. M. Harris, and D. F. , Broadcast chromatic numbers of graphs, Ars Combin, vol.86, pp.33-49, 2008.

W. Goddard and H. Xu, A note on <mml:math altimg="si27.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" xmlns:sa="http://www.elsevier.com/xml/common/struct-aff/dtd"><mml:mi>S</mml:mi></mml:math>-packing colorings of lattices, Discrete Applied Mathematics, vol.166, pp.255-262, 2014.
DOI : 10.1016/j.dam.2013.09.016

W. Goddard and H. Xu, The S-packing chromatic number of a graph, Discussiones Mathematicae Graph Theory, vol.32, issue.4, pp.795-806, 2012.
DOI : 10.7151/dmgt.1642

G. Royle, List of cubic graphs, 2015.

F. Havet, Choosability of the square of planar subcubic graphs with large girth, Discrete Mathematics, vol.309, issue.11, pp.3553-3563, 2009.
DOI : 10.1016/j.disc.2007.12.100
URL : https://hal.archives-ouvertes.fr/inria-00070223

F. Kramer and H. Kramer, A survey on the distance-colouring of graphs, Discrete Mathematics, vol.308, issue.2-3, pp.422-426, 2008.
DOI : 10.1016/j.disc.2006.11.059

R. Soukal and P. Holub, A note on packing chromatic number of the square lattice, Electron. J. Combin, 2010.

C. Von and . Conta, Torus and other networks as communication networks with up to some hundred points, IEEE Trans. Comput, issue.7, pp.32657-666, 1983.