. Moreover, -regular graph is p + 3 if and only one of its component is an odd cycle and p + 2 otherwise. So for any p, one can polynomially find the (p, 1)-total number of a 2-regular graph. If G is a connected 3-regular graph, by Proposition 1 (ii), ? 2 (G) ? 5. Moreover, Havet and Yu [2] conjecture that ? 2 (G) = 5 unless G = K 4 . This would trivially imply that the 3-Regular (2, 1)-Total Labelling Problem is polynmial time solvable. Moreover one can determine polynomially the (3, 1)-total number of a 3-regular graph. Indeed if G is 3-regular then ? 3 (G) ? 6, Proposition 1 (ii), ? 3 (G) ? 7 as proved by Havet and Yu [2], and ? 3 (G) = 6 if and only if G is bipartite below

L. , G. In, and {. .. , Then one can easily see that every vertex msut be coloured in {0, 1, p + k ? 1, p + k}. Let A, (resp. B) be the set of vertices of H labelled with 0 or p + k ? 1, (resp. 1 or p + k ? 1). Then A and B are stable sets since the endvertices of an edge may not be labelled with 0 and p + k ? 1 or p + k and 1. So (A, B) is a bipartition of G, Proof: If G is bipartite References [1] M. R. Garey and D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co, 1979.

F. Havet and M. Yu, )-total labelling of graphs, Discrete Math, issue.1, 2007.

C. J. Mcdiarmid and A. Sánchez-arroyo, Total colouring regular bipartite graphs is NP-hard, Discrete Math, pp.155-162, 1994.

A. Sánchez-arroyo, Determining the total colouring number is np-hard, Discrete Mathematics, vol.78, issue.3, pp.315-319, 1989.

T. J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing , STOC '78, pp.216-226

I. Unité-de-recherche-inria-sophia and . Antipolis, route des Lucioles -BP 93 -06902 Sophia Antipolis Cedex (France) Unité de recherche INRIA Futurs : Parc Club Orsay Université -ZAC des Vignes 4, 2004.

I. Unité-de-recherche and . Lorraine, Technopôle de Nancy-Brabois -Campus scientifique 615, rue du Jardin Botanique -BP 101 -54602 Villers-lès-Nancy Cedex (France) Unité de recherche INRIA Rennes : IRISA, Campus universitaire de Beaulieu -35042 Rennes Cedex (France) Unité de recherche INRIA Rhône-Alpes : 655, avenue de l'Europe -38334 Montbonnot Saint-Ismier (France) Unité de recherche INRIA Rocquencourt, Domaine de Voluceau -Rocquencourt -BP 105 -78153 Le Chesnay Cedex