Cécile Amblard
email: cecile.amblard@upmf-grenoble.fr

Stéphane Girard
email: stephane.girard@imag.fr

Estimation procedures for a semiparametric family of bivariate copulas

Keywords: Copulas, nonparametric estimate, measures of association, high probability regions

In this paper, we propose simple estimation methods dedicated to a semiparametric family of bivariate copulas. These copulas can be simply estimated through the estimation of their univariate generating function. We take profit of this result to estimate the associated measures of association as well as the high probability regions of the copula. These procedures are illustrated on simulations and on real data.

Introduction

The theory of copulas provides a relevant tool to build multivariate probability laws, from fixed margins and required degree of dependence. From Sklar's Theorem [START_REF] Sklar | Fonctions de répartition à n dimensions et leurs marges[END_REF], the dependence properties of a continuous multivariate distribution H can be entirely summarized, independently of its margins, by a copula, uniquely associated with H. Several families of copulas, such as Archimedian copulas [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF] or copulas with polynomial sections [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF][START_REF] Nelsen | Bivariate copulas with cubic sections[END_REF] have been proposed. More recently, we proposed to give up the polynomial form to work with a semiparametric family of copulas [START_REF] Amblard | Symmetry and dependence properties within a semiparametric family of bivariate copulas[END_REF][START_REF] Amblard | A new bivariate extension of FGM copulas[END_REF]. This permits to increase the dependence degree and to preserve the dependence properties of copulas with polynomial sections without significantly complexifying the model. Furthermore, the family of copulas is generated as simply as Archimedian copulas, that is by an univariate function.

Among the numerous papers dedicated to the construction of copulas, very few of them propose some associated inference procedures. Besides, starting from data, it is very difficult to find "Which copula is the right one?", see [START_REF] Durrleman | Which copula is the right one?[END_REF] for a review on this problem in the financial modeling context. The first attempt to estimate copulas is achieved in [START_REF] Deheuvels | La fonction de dépendance empirique et ses propriétés. Un test non paramétrique d'indépendance[END_REF] with the introduction of nonparametric estimates based on empirical copulas. A recent contribution to the nonparametric estimation of copula for time series is presented in [START_REF] Scaillet | Nonparametric estimation of copulas for times series[END_REF]. An alternative approach is to choose a parametric family of copulas and to estimate the parameters by a maximum likelihood method [START_REF] Joe | The estimation method of inference functions for margins for multivariate models[END_REF]. Both approaches suffer from their own drawbacks. In the first case, a fully nonparametric estimate is likely to suffer from the so-called "curse of dimensionality". It would have a high variance for large number of margins and moderate size of datasets. At the opposite, a parametric estimate can lead to a very high bias if the prior family of copulas is not appropriate. Restricting to Archimedian copulas, Genest & Rivest [START_REF] Genest | Statistical inference procedures for bivariate Archimedean copulas[END_REF] proposed a semiparametric estimate. In this family, estimating the copula reduces to estimating the generating function. It is therefore realistic to consider a nonparametric estimate of this univariate function. Here, we show that, similarly, the estimation of a copula in the semiparametric family [START_REF] Amblard | Symmetry and dependence properties within a semiparametric family of bivariate copulas[END_REF] can be simply achieved by estimating nonparametrically the univariate generating function. This permits to overcome the curse of dimensionality. We deduce of this estimator some statistical procedures for estimating the associated dependence coefficients and high probability regions.

In section 2, the expression of the considered semiparametric family of copulas is given and its basic properties are recalled. Section 3 is dedicated to the estimation of the generating function and of the dependence coefficients. In section 4, we address the problem of estimating high probability regions. All the proposed estimates are experimented on simulated samples in section 5 and on real data in section 6.

Definition and basic properties

Throughout this paper, we note I = [0, 1]. A bivariate copula defined on the unit square I 2 is a bivariate cumulative distribution function with univariate uniform I margins. Equivalently, it must satisfy the following properties :

(P1) C(u, 0) = C(0, v) = 0, ∀(u, v) ∈ I 2 , (P2) C(u, 1) = u and C(1, v) = v, ∀(u, v) ∈ I 2 , (P3) ∆(u 1 , u 2 , v 1 , v 2 ) = C(u 2 , v 2 ) -C(u 2 , v 1 ) -C(u 1 , v 2 ) + C(u 1 , v 1 ) ≥ 0, ∀(u 1 , u 2 , v 1 , v 2 ) ∈ I 4 , such that u 1 ≤ u 2 and v 1 ≤ v 2 .
Let us recall that, from Sklar's Theorem [START_REF] Sklar | Fonctions de répartition à n dimensions et leurs marges[END_REF], any bivariate distribution with cumulative distribution function H(x, y) and marginal cumulative distribution functions F (x) and G(y) can be written H(x, y) = C(F (x), G(y)), where C is a copula. This result justifies the use of copulas for building bivariate distributions.

Here, we consider the semiparametric family of functions defined on I 2 by:

C θ,φ (u, v) = uv + θφ(u)φ(v), θ ∈ [-1, 1], (2.1)
where φ is a function on I. This family was first introduced in [START_REF] Rodríguez Lallena | Estudio de la compabilidad y diseño de nuevas familias en la teoria de cópulas[END_REF], chapter 3, and is a particular case of Farlie's family [START_REF] Farlie | The performance of some correlation coefficients for a general bivariate distribution[END_REF]. It is extensively studied in [START_REF] Amblard | A semiparametric family of symmetric bivariate copulas[END_REF][START_REF] Amblard | Symmetry and dependence properties within a semiparametric family of bivariate copulas[END_REF]. In particular, the following basic lemma is proved:

Lemma 1 φ generates a parametric family of copulas {C θ,φ , θ ∈ [-1, 1]} if and only if it satisfies the following conditions :

(i) φ(0) = φ(1) = 0, (ii) |φ(x) -φ(y)| ≤ |x -y| for all (x, y) ∈ I 2 .
The function φ plays a role similar to the generating function in Archimedian copulas [START_REF] Genest | Copules archimédiennes et familles de lois bidimensionnelles dont les marges sont données[END_REF]. Each copula C θ,φ is entirely described by the univariate function φ and the parameter θ, which tunes the dependence between the margins. For instance, φ(x) = x(1-x) generates the Farlie-Gumbel-Morgenstern (FGM) family of copulas [START_REF] Morgenstern | Einfache Beispiele Zweidimensionaler Verteilungen[END_REF], which contains all copulas with both horizontal and vertical quadratic sections [START_REF] Quesada-Molina | Bivariate copulas with quadratic sections[END_REF]. Another example is φ(x) = x(1 -x)(1 -2x) which defines the parametric family of symmetric copulas with cubic sections proposed in [START_REF] Nelsen | Bivariate copulas with cubic sections[END_REF], equation (4.4). Of course, it is also possible to choose φ so as to define new copulas, see section 5 for an example.

3 Estimation of the generating function

Preliminaries

Let (X, Y ) be a random pair from the cumulative distribution function H(x, y) = C θ,φ (F (x), G(y)),

where F (x) and G(y) are respectively the cumulative distribution functions of X and Y . The estimation of the copula reduces to estimating the generating function φ and the parameter θ.

This estimation clearly suffers from an identifiability problem since, for instance, replacing φ by φ/ √ α and θ by αθ for any positive α leads to the same copula. When θ = 0, introducing

s = θ/|θ| and ψ = |θ|φ yields C θ,φ (u, v) = C s,ψ (u, v) = uv + sψ(u)ψ(v), (3.1)
where ψ satisfies the conditions of Lemma 1 and s ∈ {-1, 1}. The identifiability problem is not fully overcome with the new parameterization (3.1) since the sign of ψ cannot be identified.

Thus, we limit ourselves to the Positively Quadrant Dependent (PDQ) context. Recall that X and Y are PQD [START_REF] Joe | Multivariate models and dependence concepts[END_REF], section 2.1.1, if and only if

∀(x, y) ∈ R 2 , P (X ≤ x, Y ≤ y) ≥ P (X ≤ x)P (Y ≤ y).
As shown in [START_REF] Amblard | Symmetry and dependence properties within a semiparametric family of bivariate copulas[END_REF], theorem 3, X and Y are PQD if and only if

θ > 0 and, either ∀u ∈ I, φ(u) ≥ 0 or ∀u ∈ I, φ(u) ≤ 0. (3.2)
If (X, Y ) are PQD, then the copula (3.1) can always be rewritten as:

C 1,ψ (u, v) = uv + ψ(u)ψ(v), (3.3)
where ψ is a non negative function satisfying the conditions of Lemma 1. In the following, we limit ourselves to the estimation of C 1,ψ , or equivalently to the estimation of ψ in this context.

We refer to section 7 for possible improvements of the estimation method.

Estimation of ψ(w)

Let {(x i , y i ), i = 1, . . . , n} a sample of (X, Y ) from the cumulative distribution function H(x, y).

The rank transformations u i = Rank(x i )/n and v i = Rank(y i )/n yield an approximate sample from the copula C 1,ψ (u, v). The estimation of ψ(w) relies on the pseudo-observations

w i = max(u i , v i ), i = 1, . . . , n which have the common distribution function C 1,ψ (w, w) = w 2 + ψ 2 (w).
In order to obtain a regular estimated function, this estimate is written as a linear combination of a denombrable set A of functions:

ψ(w) = k∈A a k e k (w). (3.4)
The set of functions {e k (w), w ∈ I, k ∈ A} need not to be orthogonal but the condition e k (0) = e k (1) = 0 is required for all k ∈ A in order to ensure ψ(0) = ψ(1) = 0, and thus to respect condition (i) of Lemma 1. Introducing w 1,n ≤ • • • ≤ w n,n the ordered statistics associated to the w i , i = 1, . . . , n, the coefficients a k are determined by the constrained least-square problem

â = arg min M a -b 2 , 0 ≤ (M a) i , -1 ≤ (M ′ a) i ≤ 1, i = 1, . . . , n (3.5)
where M and M ′ are two matrices such that

M i,k = e k (w i,n ) , M ′ i,k = e ′ k (w i,n ) for k ∈ A, i ∈ {1, . . . , n}, and b is a vector defined by b i = (i/(n + 1) -w 2 i,n ) 1/2 , i ∈ {1, . . . , n}. The minimization of M a -b 2 ensures that for all i = 1, . . . , n ψ(w i,n ) 2 = C 1,ψ (w i,n , w i,n ) -w 2 i,n ≈ i/(n + 1) -w 2 i,n . (3.6)
The positivity conditions 0 ≤ (M a) i impose that 0 ≤ ψ(w i,n ), and the bound conditions

-1 ≤ (M ′ a) i ≤ 1 are interpreted as | ψ ′ (w i,n )| ≤ 1 which allows to fulfil Lemma 1(ii).
In practice, the optimization process provides reasonably sparse solutions, that is vectors a with a moderate number of nonzero components.

Estimation of an association measure

Two measures of association between the components of the random pair (X, Y ) are usually considered [START_REF] Joe | Multivariate models and dependence concepts[END_REF], section 2.1.9. The Kendall's Tau is the probability of concordance minus the probability of discordance of two random pairs (X 1 , Y 1 ) and (X 2 , Y 2 ) described by the same joint bivariate law H(x, y) = C(F (x), G(y)). It only depends on the copula:

τ = 4 I 2 C(u, v)dC(u, v)-1. (3.7)
The Spearman's Rho is the probability of concordance minus the probability of discordance of two pairs (X 1 , Y 1 ) and (X 2 , Y 2 ) with respective joint cumulative law H(x, y) and F (x)G(y),

ρ = 12 I 2 C(u, v)dudv-3.
In [START_REF] Amblard | Symmetry and dependence properties within a semiparametric family of bivariate copulas[END_REF], proposition 1, it is shown that, within the family (2.1), these two measures are equivalent up to a scale factor: 2ρ = 3τ . Here, we focus on the Spearman's Rho whose expression is in our family:

ρ = 12θ I φ(u)du 2 = 12 I ψ(u)du 2 .
We then propose an estimate based on the estimate ψ:

ρSP = 12 k∈A a k β k 2 , (3.8)
where we have introduced β k = I e k (u)du. This integral can be calculated analytically or numerically by Simpson's rule, depending on the complexity of the basis of functions. It is also possible to estimate ρ in a nonparametric way by rescaling the empirical version of (3.7)

introduced in [START_REF] Genest | Statistical inference procedures for bivariate Archimedean copulas[END_REF] with the factor 3/2 to obtain:

ρNP = 6 n(n -1) n i=1 n j=1 1{u j < u i , v j < v i } - 3 2 ,
where 1{.} is the indicator function. The two estimates ρSP and ρNP are compared on simulations in section 5.

Estimation of high probability regions 4.1 The general problem

Let us recall the definition of a p-dimensional α-quantile of a distribution P . Let S the class of Borel measurable sets of R p and let λ be the Lebesgue measure defined on S:

Q α = inf{λ(S) : P (S) ≥ α, S ∈ S}, 0 < α ≤ 1.
Here, Q α is the minimum volume S ∈ S that contains at least a fraction α of the probability mass. This is a particular case of the general quantile function introduced by Einmal and Mason [START_REF] Einmal | Generalized quantile process[END_REF]. A particular attention has been paid to the estimation of Q 1 , the support of the distribution, from a sample {M 1 , . . . , M n } of R p . The early paper of Geffroy [START_REF] Geffroy | Sur un problème d'estimation géométrique[END_REF] takes place in the case p = 2 and the considered supports are written

Q 1 = {(x, y) ∈ R 2 : 0 ≤ x ≤ 1 ; 0 ≤ y ≤ f (x)},
where f is an unknown function. More recently, smooth estimates of the frontier function f have been proposed [START_REF] Girard | Projection estimates of point processes boundaries[END_REF] and their extension to star-shaped supports has been studied [START_REF] Jacob | Regression and edge estimation[END_REF]. Numerous works have been dedicated to the nonparametric estimate

Q 1 = n i=1 B(M i , r n ),
where B(M i , r n ) is the ball of radius r n and centered at M i , see for instance [START_REF] Devroye | Detection of abnormal behavior via non parametric estimation of the support[END_REF][START_REF] Gensbittel | Contribution à l'étude statistique de répartitions ponctuelles aléatoires[END_REF]. In the latter paper, a partition based estimate is also proposed. Introducing {K i } i≥1 a partition of R 2 , the estimate is simply:

Q 1 = i,j K i 1{M j ∈ K i }.
In subsection 4.2, we propose an estimate of Q α , α < 1, when P is a bivariate copula, with a similar principle. Subsection 4.3 examines the special case of the semiparametric family of copulas {C 1,ψ }. The estimation of such high probability regions is of particular interest for bivariate copulas since some dependence properties can be read on this graph, see [START_REF] Long | Geometry of a correlation coefficient under a copula[END_REF]. To this end, introduce the two diagonal lines ℓ 1 : v = u and ℓ 2 : v = 1 -u of the unit square I 2 . If the graph of Q α is nearly symmetric with respect to both diagonals ℓ 1 and ℓ 2 then the copula models weakly dependent variates. On the contrary, if the graph is concentrated along ℓ 1 , then the copula models strongly positively dependent variates.

The algorithm

Q α = k,ℓ K k,ℓ 1{δ k,ℓ = 1}, (4.1)
where the δ k,ℓ are defined by the optimization problem

min 1 N 2 N k=1 N ℓ=1 δ k,ℓ , (4.2)
under the constraints δ k,ℓ ∈ {0, 1} and

N k=1 N ℓ=1 δ k,ℓ P (K k,ℓ ) ≥ α. (4.
3)

The quantity P (K k,ℓ ) is an estimation of the probability P (K k,ℓ ). The quality of the estimate Q α strongly depends on the quality of this estimate. This is discussed in subsection 4.3. Let us note that (4.2) is equivalent to minimizing λ( Q α ) and (4.3) corresponds to the constraint

P ( Q α ) ≥ α.
This optimization problem can be solved with a simple algorithm. The first step consists to sorting the estimated probabilities P (K k,ℓ ) in decreasing order to obtain the sequence Pτ , τ = 1, . . . , N 2 . The second step is the computation of the number of subsets of the partition which are going to be used:

J = min j, j τ =1 Pτ ≥ α .
The last step is the selection of the J first subsets: δ k,ℓ = 1 if 1 ≤ τ (k, ℓ) ≤ J, which leads to the estimate (4.1).

Estimation of P (K k,ℓ )

If no information is available on the distribution P , one can use the nonparametric estimate

P NP (K k,ℓ ) = 1 n n i=1 1{M i ∈ K k,ℓ }.
Now, restricting ourselves to the family {C 1,ψ } allows to consider semiparametric estimates, which are much more accurate than the nonparametric one. Taking into account of (3.3), it follows that

P (K k,ℓ ) = C 1,ψ k N , ℓ N -C 1,ψ k -1 N , ℓ N -C 1,ψ k N , ℓ -1 N + C 1,ψ k -1 N , ℓ -1 N = 1 N 2 + ψ k N -ψ k -1 N ψ ℓ N -ψ ℓ -1 N .
Thus, basing on section 3, the following semiparametric estimate can be introduced

P SP (K k,ℓ ) = 1 N 2 + ψ k N -ψ k -1 N ψ ℓ N -ψ ℓ -1 N .
The results using P SP and P NP are compared on simulations in the next section.

Simulation results

All the numerical experiments of this section have been conducted on the family of copulas generated by the set of functions

∀k ≥ 1, ψ k (x) = 1 -x k + (1 -x) k 1/k , x ∈ I. (5.1)
For the sake of simplicity, the resulting family of copulas will be denoted by

C k (u, v) = C 1,ψ k (u, v).
This family is interesting since it can represent very different distributions: y) is the uniform distribution on the unit square I 2 . The associated Spearman's Rho is ρ 1 = 0.

• When k = 1, C 1 (x,
• Letting k → ∞, we obtain ψ k (x) → ψ ∞ (x) = min(x, 1 -x) for all x ∈ I. Thus, it appears that C ∞ (x, y) is a mixture of two uniform distributions on the squares [0, 1/2] 2
and [1/2, 1] 2 with mixing parameter 1/2. The associated Spearman's Rho is ρ ∞ = 3/4, the maximum value in the family (2.1).

• When 1 < k < ∞, we get a bivariate distribution "interpolating" between the two previous one. Up to our knowledge, it is not possible to calculate ρ k explicitly.

Simulation of data from the copula

The simulation method described in [START_REF] Nelsen | An introduction to copulas[END_REF], p. 36 is used. First, two independent uniform samples u i and t i , i = 1, . . . , n are simulated. Second, for each i = 1, . . . , n, v i is computed such that

t i = ∂ ∂u C k (u i , v i ),
by a dichotomy procedure. The resulting sample (u i , v i ), i = 1, . . . , n has joint distribution function C k (u, v).

Estimation of the generating function

In this paragraph, we have chosen n = 100. Starting from the sample (u i , v i ), i = 1, . . . , n, the generating function is estimated using the procedure described in section 3. The chosen basis of functions is doubly-indexed by a scale parameter s and a location parameter ℓ:

e s,ℓ (x) = sin π 2 (2 s+1 x -ℓ) 1{2 s+1 x ∈ [ℓ, ℓ + 2]}, (s, ℓ) ∈ A, (5.2)
where A = {(s, ℓ), 0 ≤ ℓ ≤ 2(2 s -1), 0 ≤ s}. See figure 1 for a graph of the first basis functions.

In figure 2, the estimation of ψ 2 (x), ψ 4 (x) and ψ 8 (x) is compared to the true generating functions.

These first results are visually satisfying. The optimization procedure selects about 30 basis functions. A more precise comparison is achieved in table 1 by repeating each estimation on 100 different samples. On the basis of these 100 repetitions, the mean value and the standard deviation of the L 2 error

ε = I (ψ k (x) -ψk (x)) 2 dx 1/2
are evaluated, as well as the mean value and the standard deviation of the two estimates ρSP and ρNP of the Spearman's rho. The integral appearing in ρ k is calculated numerically using

Simpson's rule. The computation of ρSP is based on (3.8) and is thus explicit after remarking that β s,ℓ = I e s,ℓ (x)dx = 2 1-s /π.

The mean values of ε (about 10 -2 ) confirm that the function ψ k is correctly estimated. Moreover it appears that the semi parametric estimation of the Spearman's Rho is better than the non parametric estimate, excepted for the case k = 1. The standard deviations are similar for the two estimates.

Estimation of high probability regions

Starting from the estimations of ψ 2 (x), ψ 4 (x) and ψ 8 (x) obtained above, it is possible to estimate high probability regions Q α with the procedure described in section 4. The following probabilities α = 0.25, α = 0.5 and α = 0.75 are considered. Here, the regions obtained using the semiparametric estimate P SP , the nonparametric estimate P NP and the true probability P can be compared. Of course, this probability depends on ψ(x) and cannot be used in practical situations. Here n = 500 and the estimated regions are obtained by a discretisation on a N × N grid with N = 30 when using P SP or P and N = 8 when using P NP so as to obtain approximatively 500/64 ≃ 8 points in each cell. The results are presented on figures 3-5. It is apparent that the estimations obtained with the true probability P and its semiparametric estimate P SP are very close, especially for moderate values of k. This confirms the results obtained in the previous paragraph. On the contrary, the nonparametric estimate accuracy is very poor for such values of the sample size n. We can also observe that, as k increases, the high probability regions are more and more concentrated in the neighborhood of the ℓ 1 diagonal line. This, together with 1, illustrates the property that the positive dependence is increasing with k.

Real data

The dataset consists of n = 225 countries on which two variables have been measured: X, the life expectancy at birth (years) in 2002 of the total population and Y , the difference between the life expectancy at birth of women and men. The data is available on the following web-site:

http://www.odci.gov/cia/publications/factbook/. According to the PQD test proposed in [START_REF] Scaillet | A Kolmogorov-Smirnov type test for positive quadrant dependence[END_REF], these data are PQD. The first step is to compute the rank transformations u i = Rank(x i )/n and v i = Rank(y i )/n, see figure 7. Then, the generating function ψ(x) is estimated using the basis (5.2). The optimization procedure yields an expansion of ψ(x) with respect to 24 basis functions. The function ψ(x) is plotted in figure 6. The estimated Spearman's rho are ρNP = 52.4% and ρSP = 40.7%. These values seem to confirm a moderate positive dependence between the two variables. The higher the life expectancy is, the more important the difference between women and men is. Finally, one can estimate the high probability regions. The same parameters as in the simulation section are used. The results are presented in figure 7. Of course, since the true function ψ(x) is not known (and perhaps does not exist), it is only possible to compare the estimations obtained with the nonparametric and semiparametric estimates P NP and P SP . The semiparametric estimation reveals two main groups of countries. In the first one, both men and women share a small life expectancy with weak differences between sexes.

In the second one, both men and women share a large life expectancy but with important differences between sexes. The sample size is not large enough to obtain meaningful results with the nonparametric estimate.

×10 -2 ×10 -2 ×10 -2 ×10 -2 ×10 -2 ×10 -2 ×10 -2

Let

  {I k , k = 1, . . . , N } be the equidistant N -partition of I and K k,ℓ = I k × I ℓ the associated N ×N grid. Denote δ k,ℓ ∈ {0, 1}, k = 1, . . . , N , ℓ = 1, . . . , N a binary N ×N array and introduce the estimate

Figure 1 :

 1 Figure 1: Graph of the first basis functions of (5.2). Solid line: e 0,0 (x), dotted line: e 1,0 (x), dashdot line: e 1,1 (x), dashed line: e 1,2 (x).

  SP ) std(ρ SP ) mean(ρ NP ) std(ρ NP ) mean(ε) std(ε)

Figure 2 :Figure 3 :Figure 5 :Figure 6 :

 2356 Figure 2: Comparison of the true generating functions ψ k (x) defined by (5.1) and the estimated ones ψk (x). Solid line: k = 2, dashed line: k = 4, dashdot line: k = 8.

Figure 7 :

 7 Figure 7: Estimation of high probability regions Q α from real data. Dark Grey: α = 0.25, grey: α = 0.5, light grey: α = 0.75. Top left: real data, top right: real data after rank transformation, bottom left: nonparametric estimate, bottom right: semiparametric estimate.

Table 1 :

 1 Estimation of the generating function and of the Spearman's Rho (ρ k ). The mean value and the standard deviation of the L 2 error ε as well as of the estimates ρSP and ρNP are evaluated on 100 repetitions.

	1	0	0.81	(6.62)	0.18	(11.0)	8.75	(3.58)
	2 42.5	43.0	(9.91)	41.2	(9.11)	3.67	(1.26)
	4 66.4	65.8	(7.11)	64.3	(6.11)	3.01	(1.33))
	6 71.2	70.6	(7.60)	68.8	(6.09)	3.10	(1.35)
	8 72.8	72.1	(7.68)	70.2	(6.05)	3.10	(1.17)

Acknowledgement

The authors are indebted to the anonymous referees for their helpful comments and suggestions.

They have contributed to a great improvement of this paper.

Further work

We have presented a method for estimating copulas in the bivariate family of copulas C s,ψ (u, v) in the PQD case. Even though a test [START_REF] Denuit | Non parametric tests for positive quadrant dependence[END_REF][START_REF] Scaillet | A Kolmogorov-Smirnov type test for positive quadrant dependence[END_REF] has not rejected the PQD assumption, deciding if the copula model C s,ψ (u, v) is adapted to a particular dataset is an opened problem. It could be possible to build a goodness-of-fit test based on the comparison of the estimations ρNP ρSP . The test would reject the model C s,ψ (u, v) if the difference |ρ NP -ρSP | is too large. If the PQD assumption is rejected, the proposed estimation method cannot be used. To overcome the identifiability problem, a possible modification of the method would be to replace the projection step (3.4) by the selection of the function ψ in a database leading to the best approximation (3.6).


Mahdad Khatirinejad
email: mahdad.khatirinejad@tkk.fi

Reza Naserasr

Mike Newman
email: mnewman@uottawa.ca

Ben Seamone

Brett Stevens

Naserasr, Newman, Seamone, Stevens Khatirinejad

Vertex-colouring edge-weightings with two edge weights

Keywords:

An edge-weighting vertex colouring of a graph is an edge-weight assignment such that the accumulated weights at the vertices yields a proper vertex colouring. If such an assignment from a set S exists, we say the graph is S-weight colourable. It is conjectured that every graph with no isolated edge is {1, 2, 3}-weight colourable.

We explore the problem of classifying those graphs which are {1, 2}-weight colourable. We establish that a number of classes of graphs are S-weight colourable for much more general sets S of size 2. In particular, we show that any graph having only cycles of length 0 mod 4 is S-weight colourable for most sets S of size 2. As a consequence, we classify the minimal graphs which are not {1, 2}-weight colourable with respect to subgraph containment. We also demonstrate techniques for constructing graphs which are not {1, 2}-weight colourable.

Introduction

Let G be a simple graph and S be a set of real numbers. An S-edge-weighting of G is an assignment w : E(G) → S. Given an S-edge-weighting, the weighted degree of a vertex v, denoted w(v), is the sum of weights of the edges incident with v. An S-edge-weighting gives a vertex colouring if the weighted degrees of adjacent vertices are different. If an S-edge-weighting vertex colouring w exists, we also call w an S-weight colouring and we say G is S-weight colourable. For a positive integer k, we say G has a k-weight colouring or G is k-weight colourable if it is S-weight colourable for every set S of size k. The most commonly studied sets S are those of the form {1, . . . , k}.

Problem 1 Given a graph G with no isolated edges, find the minimum k such that G is {1, . . . , k}-weight colourable.

colourability of bipartite graphs in Section 3 and of other general classes of graphs, particularly direct products of graphs, in Section 4. Of note, we show in Section 3 that if every cycle of G is of length 0 mod 4, then G is {1, 2}-weight colourable.

2 Building blocks: Weight colourings of basic graphs

We will use standard graph theory terminology; the reader may refer to [START_REF] Bondy | Graph Theory[END_REF] for clarification of any terms which are not specifically defined here.

The length of a path (walk) is defined to be the number of edges of the path (walk). A thread in a graph G is a walk connecting two vertices x and y, not necessarily distinct, such that the internal vertices are distinct from all others on the walk, all internal vertices have degree 2 in G, and deg(x), deg(y) ≥ 3. If x and y are distinct, then the walk is in fact a path and in this case we may refer to the thread as an ear. If the condition that deg(x), deg(y) ≥ 3 is changed to deg(x), deg(y) ≥ 2 in either case, we have a subthread or subear respectively.

A cut vertex of a graph is one whose removal disconnects the graph. A graph is 2-connected if it has no cut vertex. A graph (not necessarily simple) is called separable if it can be decomposed into two nonempty subgraphs with exactly one vertex in common. A simple graph is separable if and only if it is not 2-connected. A maximal nonseparable subgraph of G is a block of G. Note that a block is isomorphic either to K 2 or to a 2-connected graph. An end block of G is a block which contains at most one cut vertex of G.

A graph is c-colourable if the vertices can be coloured with c colours so that adjacent vertices get different colours.

K n and C n , respectively, denote the complete graph and the cycle on n vertices. The Cartesian product of two graphs G and H, denoted by G 2 H, is defined as the graph having vertex set V (G)×V (H) where two vertices (u, u ) and (v, v ) are adjacent if and only if either u = v and u is adjacent to v in H or u = v and u is adjacent to v in G.

We present a few simple observations. Proposition 2.1 Let a, b, t be nonzero real numbers and G a graph. Then (i) G is {a, b}-weight colourable if and only if G is {at, bt}-weight colourable, and

(ii) if G is {a, b}-weight colourable then G is {p, q}-weight colourable for any nonzero p, q ∈ R which are linearly independent over Q.

Proof: (i) This follows from the fact that w(u) = w(v) if and only if t • w(u) = t • w(v). (ii) Note that if two adjacent vertices receive distinct linear combinations of a and b as weights, then the coefficients of these linear combinations will suffice for any two linearly independent nonzero reals. 2

From Proposition 2.1 we deduce the following, adopting the convention that 0 and 1 are relatively prime integers:

Corollary 2.2 A graph G is 2-weight colourable if and only if G is {a, b}-weight colourable for every pair of relatively prime integers a and b.

Proposition 2.1 allows us to reduce our proofs of positive results on the existence of {a, b}-weight colourings of a graph to relatively prime integers. Results in which we show that G does not admit an {a, b}-weight colouring will not rely on such assumptions -we will prove them for all real a, b.

Proposition 2.3 If G is d-regular and {a, b}-weight colourable for a fixed choice of a and b then (i) it is d-colourable, and (ii) it is 2-weight colourable.

Proof: (i) The weighted degree of each vertex must be a number of the form ta + (d -t)b for some 0 ≤ t ≤ d, and a vertex of weighted degree da cannot be adjacent to a vertex of weighted degree db. Thus putting the vertices of weighted degree da or db in the same colour class gives a d-colouring.

(ii) In an {a, b}-edge weighting of a d-regular graph, the accumulated weight at any vertex is in a oneto-one correspondence with the number of incident edges of weight a. Thus if one choice of a and b gives a vertex colouring, then any other choice of a and b will as well.

2

Corollary 2.4 If χ(G) = ∆(G) + 1 or, equivalently (by Brooks theorem), if G is an odd cycle or a complete graph then G is not S-weight colourable for any set S of size 2.

Even though the complete graph is not S-weight colourable for any set of size 2, it has an S-edgeweighting that is very close to being an S-weight colouring. This specific weighting will be useful in constructing families of 2-weight colourable graphs and non-2-weight colourable graphs in Section 4.

Lemma 2.5 Given n ≥ 2 and a = b ∈ R, there is an {a, b}-edge-weighting of K n such that the weighted degrees of all the vertices are distinct except for 2 of them. Furthermore, in any such {a, b}edge-weighting, the degree sequence of the subgraph induced by the edges of weight a (as well as the subgraph induced by the edges of weight b) is either

(1, 2, . . . , n 2 -1, n 2 , n 2 , n 2 + 1, . . . , n -2, n -1), or (0, 1, . . . , n 2 -2, n 2 -1, n 2 -1, n 2 , . . . , n -3, n -2).
Proof: We prove the first part with an explicit construction. Choose any two vertices and assign weight a to the edge joining them. Choose a new vertex and assign weight b to all the edges joining this vertex to the previous two vertices. Choose another vertex and assign weight a to all the edges joining this vertex to the previous three vertices. By repeating this process until all vertices are exhausted, we achieve the desired edge-weighting since the two vertices chosen first will have the same weight while the remainder of the graph is properly coloured. Note that we achieve the same result by swapping a and b in this argument. We prove the second part of the lemma by induction on n. Suppose w is such an edge-weighting of K n and let w(u) = w(v). It is easy to verify the claim for n = 2 and n = 3. If w(x) / ∈ {(n -1)a, (n -1)b} for every vertex x then w(x) can only take n -2 values, a contradiction to the choice of w. If w(u) = w(v) ∈ {(n -1)a, (n -1)b} then by removing u and v, w induces an {a, b}-weight colouring of K n-2 , a contradiction to Corollary 2.4. Thus there exists a vertex x = u, v such that w(x) ∈ {(n-1)a, (n-1)b}. The claim follows by induction on K n -x.

2

The following technical lemmata will be useful for the rest of the paper, since they establish useful tools for finding edge-weighting vertex colourings of graphs with specific structural properties.

Lemma 2.6 Suppose G has a vertex v with a set of leaf neighbours L where |L| ≥ deg(v)/2 . Let a = b be real numbers with ab > 0. If G \ L is {a, b}-weight colourable, then so is G.

Proof: As mentioned, Proposition 2.1 allows us to only consider a, b ∈ Z + . Suppose w is an {a, b}weight colouring of G \ L. The possible extensions of w to G give exactly |L| + 1 possible weights for v. Since v has at most |L| neighbours in G \ L, in at least one of the extensions, the weighted degree of v is different from the weighted degrees of the neighbours of v in G \ L. The weighted degree of v is also different from the weighted degrees of the neighbours of v in L, since ab > 0.

2

Corollary 2.7 Every tree with at least 3 vertices is {a, b}-weight colourable, where a = b are real numbers with ab > 0.

Proof: The statement holds for any star, K 1,n-1 , since the assignment of a to all edges achieves the desired result. As such the result holds for n = 3 since the unique tree on 3 vertices is a star. Let T be a tree on n vertices which is not a star and assume the result holds for any tree with fewer than n vertices. Every tree has a vertex v that has at least deg(v)/2 leaf neighbours. Since T is not a star, removing the leaf neighbours of v gives a subtree T on at least 3 vertices. By the induction hypothesis T has an {a, b}-weight colouring. By Lemma 2.6, T does as well. 2

The following lemma establishes that we may contract long threads in a way that maintains weight colourability.

Lemma 2.8 Let G be a graph, P = v 0 , e 1 , v 1 , e 2 , v 2 , e 3 , v 3 , e 4 , v 4 , e 5 , v 5 be a subthread of G, and a = b be any two real numbers. Let G = G/{e 1 , e 2 , e 3 , e 4 } Then, (i) If w is an {a, b}-weight colouring of G, then w(e 1 ) = w(e 5 ) = w(e 3 ).

(ii) If G is {a, b}-weight colourable, then so is G.

(iii) If deg(v 0 ) = 2 or deg(v 5 ) = 2, then G is {a, b}-weight colourable if and only if G is {a, b}-weight colourable.
Proof: (i) If w(e 1 ) = w(e 5 ) then either one of the two choices for w(e 3 ) results in an improper colouring at e 2 or e 4 . Hence w(e 1 ) = w(e 5 ) and w(e 3 ) must be distinct.

(ii) For convenience, we still denote the vertex obtained from the contraction by v 0 . Suppose w is an {a, b}-weight colouring of G . Then w (v 0 ) = w (v 5 ). Without loss of generality assume w (v 0 v 5 ) = a. Let w(e) = w (e) for each e / ∈ {e 1 , e 2 , e 3 , e 4 , e 5 }, w(e 1 ) = w(e 5 ) = a and w(e 3 ) = b. There are two possibilities for the weights of e 2 and e 4 . Assigning w(e 2 ) = a and w(e 4 ) = b does not yield a proper vertex colouring of G if and only if either w(v 0 ) = 2a or w(v 5 ) = a + b. Similarly, defining w(e 2 ) = b and w(e 4 ) = a does not yield a proper vertex colouring of G if and only if either w(v 0 ) = a + b or w(v 5 ) = 2a. Suppose that neither weighting works. If the first possibility gives w(v 0 ) = 2a, then the second must give w(v 5 ) = 2a. If the first possibility gives w(v 5 ) = a + b, then the second gives w(v 0 ) = a + b. In either case w(v 0 ) = w(v 5 ), a contradiction.

(iii) Assume deg(v 0 ) = 2 and let e 0 be the other edge incident with v 0 . Suppose w is an {a, b}-weight colouring of G. By (i) we have w(e 0 ) = w(e 4 ) and w(e 1 ) = w(e 5 ). Hence w(v 0 ) = w(v 4 ) = w(v 5 ). Thus, by assigning the common weight of e 1 and e 5 to the edge v 0 v 5 , we get an {a, b}-weight colouring of G .

2

The degree condition on the ends of P in Lemma 2.8 (iii) cannot be dropped. For example, by taking G to be the path of length 5, a = 1, and b = 2, Lemma 2.8 (iii) fails.

From this lemma we may deduce necessary and sufficient conditions for the existence of {a, b}-weight colourings of cycles. Proposition 2.9 Let a and b be any distinct real numbers. Then C n is {a, b}-weight colourable if and only if n ≡ 0 (mod 4).

In lieu of a proof, we simply note that, by Lemma 2.8 (iii), the proof of this proposition may be reduced to the cases C 3 , C 4 , C 5 and C 6 . The details are left to the reader. There are {a, b}-edge weightings of other cycles of length 4k + 1, 4k + 2 and 4k + 3 which give vertex colourings with as few conflicts as possible. These results are largely technical, though not difficult to prove.

Proposition 2.10 Let a and b be any distinct real numbers. Then C 2k+1 has an {a, b}-edge weighting w such that only one edge e = uv has the property that w(u) = w(v).

Proposition 2.11 Let a and b be any distinct real numbers. Then C 4k+2 has an {a, b}-edge weighting w such that precisely two edges e = uv and e = u v have the property that w(u) = w(v) and w(u ) = w(v ). Furthermore,

• the distance between e and e is even,

• e and e may be chosen to be any two edges at an even distance, and

• if f 1 and f 2 are the edges incident to e, then their weights are equal and can be chosen to be either a or b (similar for e ).

We present a specific consequence of Proposition 2.11 which we will find useful.

Proposition 2.12 Let k be an integer, k ≥ 1. Then C 4k+2 has an {a, b}-edge-weighting such that three consecutive vertices have equal weight and the rest of the cycle is properly coloured. Furthermore, the edge-weighting can be chosen so that the weights of the four edges which contribute to the weights of those three vertices will all be a, all b, or alternate between a and b.

Let Θ (m1,...m d ) , d ≥ 3, be the graph constructed from d internally disjoint paths between distinct vertices x and y, where the i-th path has of length m i . For simplicity, we assume

m 1 ≤ m 2 ≤ • • • ≤ m d .
Such graphs will be referred to as theta graphs. We present necessary and sufficient conditions for theta graphs to be 2-weight colourable.

Theorem 2.13 Let d ≥ 3 and let a, b be real numbers. The graph Θ (m1,m2,...,m d ) is 2-weight colourable if and only if it is not of the form Θ (1,4k2+1,...,4k d +1) .

Proof: Let x and y be the two vertices of degree greater than two, and let {P i |1 ≤ i ≤ d} be the d internally disjoint paths between x and y.

Suppose w is an {a, b}-weight colouring of Θ (1,4k2+1,...,4k d +1) . By applying Lemma 2.8 (i) to each P i , we observe that on any of the d disjoint paths between x and y the first and last edges must receive same weight. Thus w(x) = w(y), a contradiction since x and y are adjacent. Hence Θ (1,4k2+1,...,4k d +1) is not {a, b}-weight colourable for any a, b.

Consider Θ (m1,m2,...,m d ) Θ (1,4k2+1,...,4k d +1) . We can assume that |a| ≥ |b|. Let n j be the number of paths that have length equivalent to j mod 4. Note that

n 0 + n 1 + n 2 + n 3 = d = deg(x) = deg(y).
For each path P i , weight each edge according to Lemma 2.8 so that the edges incident with x are weighted a. Then w(x) = da so it has no conflicts with its neighbours since d ≥ 3 and the condition on the magnitudes of a and b gives da ∈ {2a, a + b}. Note that, if |P i | ≥ 2, there are two choices for the next edge's weight on P i which determines the rest of the weights. Given one such weighting of a path P i , the effects of switching to the alternate weighting where the edge incident to x receives weight a depend on the parity of the length of the path. If |P i | is even, the weight of the edge incident to y and the vertex weights of the neighbours of x and y on P i all change. If |P i | odd, the weight of the edge incident to y remains unchanged, but the vertex weights of the neighbours of x and y on P i do change. In all cases the only possible weights on path-neighbours of x or y are 2b, a + b and 2b. We prove, by cases, that there is an appropriate set of choices which make w(y) distinct from its neighbours. n 0 + n 2 ≥ 4: Our choice of weightings for even P i 's give at least 5 possible values for w(y), so there is a choice such that w(y) ∈ {2b, a + b, 2a, da}. n 0 + n 2 = 3: If no P i has length 1, da is not a forbidden weight for y. Also, if n 3 ≥ 1 then there is an edge incident to y with weight b, and w(y) = da. In either case there is a choice of weightings so that w(y) ∈ {2b, a + b, 2a}.

So, assume that m 1 = 1 and n 3 = 0. If the initial weighting fails then we must have

{2b, a + b, 2a, da} = {(d -3)a + 3b, (d -2)a + 2b, (d -1)a + b, da} which implies that b = -(d -3)a and d ≥ 4. The fact that |a| ≥ |b| gives that d = 4, implying n 1 = 1 and b = -a.
We weight all edges explicitly. The single edge on the path of length 1 receives weight a.

If n 0 = 3 then weight the edges of one even path a, a, . . . , -a, -a and the other two a, -a, . . . , -a, a.

If n 0 = 2 and n 2 = 1 weight the edges of the paths of length 0 mod 4 with a, a, . . . , -a, -a and the other even path with a, a, . . . , a, a. If n 0 = 1 and n 2 = 2 weight the edges of the path of length 0 mod 4 with a, -a, . . . , -a, a and the two other even paths with a, -a, . . . , a, -a. Finally if n 0 = 0 and n 2 = 3 weight the edges of all even paths with a, -a, . . . , a, -a. Each weighting gives a vertex-colouring for its respective case. n 0 + n 2 = 2: If n 3 = 0 and n 0 > 0 then assign weights to the edges of one path which is length 0 mod 4 so that the weights of the first and last edges are both a. Weight the edges of the other even path so that the edge incident to x is weighted a and the edge incident to y is weighted b. If n 3 = n 0 = 0 but either d > 3 or b = 0 then assign weights to the edges of both even paths so that their edges incident with x are weighted a, one of the edges incident with y is weighted a and the other is weighted b. In both cases weight the edges of the paths of length 1 mod 4 so the weights are, in order beginning with the edge incident with x, a, a . . . b, a (if the path is a single edge, give it weight a). In the case when n 3 = n 0 = 0, d = 3 and b = 0 weight the edges of the two even paths a, 0, 0, • • • a, a, 0 and the single odd path with 0, 0, a, a, • • • a, 0 (beginning with the edge incident with x in each case). The weighting given in each case gives a proper vertex colouring.

Assume n 3 ≥ 1. If n 0 = n 2 then choose weightings for each P i so that w(x) = da and each remaining neighbour of y has accumulated weight a + b. Then w(y) = an 0 + an 1 + bn 2 + bn 3 . Since n 3 ≥ 1 we have w(x) = w(y), so the only possible conflict is if w(y) = a + b. In this case change both even P i 's to their alternate weighting, maintaining w(x) = da and producing a new weight at y:

w (y) = bn 0 + an 1 + an 2 + bn 3 = w(y) + (a -b)(n 2 -n 0 ) = a + b + (a -b)(n 2 -n 0 ) = 3a -b if n 0 = 0, n 2 = 2 3b -a if n 0 = 2, n 2 = 0
In either case w (y) = a + b. If n 0 = 2 then y has neighbours with weights 2b, and 3b -a = 2b. Similarly if n 2 = 2 then the weight at y avoids conflict with its neighbours with weight 2a.

If n 0 = n 2 = 1 we start again with choices from the basic strategy that leave all path-neighbours with weight a + b. We have w(x) = da = (n 1 + 1)a + (n 3 + 1)b = w(y). Thus the only conflict can again be if w(y) = a + b or equivalently, an 1 + bn 3 = 0. In this case we weight the edges of P i 's of lengths equivalent to 0, 1, 2, and 3 mod 4 with {a, a, . . . , b, b}, {a, b, . . . , a, a}, {a, a, . . . , a, a} and {a, b, . . . , b, b} respectively. We still have that w(y) = a + b = da = w(x) and no neighbour of y has weight a + b. n 0 + n 2 = 1: If n 3 = 0 then weight the edges of the even path so that the edge incident with x receives weight a and the edge incident with y receives weight b. Weight the edges of the paths of length 1 mod 4 so the weights are, in order beginning with the edge incident with x, a, a . . . b, a (if the path is a single edge, give it weight a). This weighting gives a proper vertex colouring. Assume n 3 ≥ 1. Again, weight the edges of each P i so that w(x) = da and each neighbor of y (distinct from x) has accumulated weight a + b. Since n 3 ≥ 1 we have that w(x) = da = w(y). If w(y) = a + b, then w is an {a, b}-weight colouring. Suppose w(y) = a + b. Equivalently

(n 0 + n 1 -1)a + (n 2 + n 3 -1)b = 0.
(1)

Change the edge weights of the even length path to begin with b, a. Call this weighting w . We now have w (x) = (d -1)a + b and w (y) = a + b. All neighbours of y still have weight a + b, so the only possible conflicts are between x and its neighbours. We reduce all potential conflicts to one of four cases, which are solved explicitly.

If w (x) = w (y) then since w (x) = (d -1)a + b, y is incident with precisely one edge with weight b. Since n 3 ≥ 1, the edge with weight b comes from a path of length 3 mod 4. This gives n 0 = 0, n 2 = 1 and n 3 = 1 and then Equation 1 and |a| ≥ |b| gives either • n 0 = 1, n 1 = 0, n 2 = 0, n 3 = 2 and b = 0 which is dealt with in case i. below.

• n 0 = 0, n 1 = 1, n 2 = 1, n 3 = 1 and b = 0 (case iii. below). • n 0 = 0, n 1 = 2, n 2 = 1, n 3 =
• n 0 = 1, n 1 = 1, n 2 = 0, n 3 = 2 and b = -a which is dealt with in case ii. below.

• n 0 = 0, n 1 = 1, n 2 = 1, n 3 = 1 and b = 0 which is dealt with in case iii. below.

• n 0 = 0, n 1 = 2, n 2 = 1, n 3 = 1 and b = -a which is dealt with in case iv. below. case i. In this case x and y are not adjacent. Weight the edges of the path of length equivalent to 0 mod 4 with 0, 0, . . . , a, a and the two odd paths with a, 0, . . . , 0, 0. case ii. In this case x and y are not adjacent. Weight the edges of the paths of lengths equivalent to 0 mod 4, 1 mod 4 and 3 mod 4 with -a, -a, . . . , a, a, a, -a, . . . , a, a and a, -a, . . . , -a, -a respectively. case iii. In this case x and y may be adjacent. Weight the edges of the paths of lengths equivalent to 1 mod 4, 2 mod 4 and 3 mod 4 with a, a, . . . , 0, a, 0, 0, . . . , 0, 0 and 0, 0, . . . , 0, a respectively. case iv. In this case x and y may be adjacent. Weight the edges of the paths of lengths equivalent to 1 mod 4, 2 mod 4 and 3 mod 4 with a, -a, . . . , a, a, -a, -a, . . . , -a, -a and a, -a, . . . , -a, -a respectively.

Each of these edge-weightings gives a proper vertex colouring.

n 0 + n 2 = 0: Every weighting of the paths P i which gives w(x) = da must give w(y) = an 1 + bn 3 . If m 1 = 1 then, since our graph is not Θ (1,4k2+1,...,4k d +1) , we have n 3 ≥ 1 and thus w(x) = w(y). Suppose m = 1. For each P i we have two choices for y's neighbour. Each choice leaves w(y) constant. Thus there is a choice for each path which gives an edge-weighting vertex-colouring. 2

Bipartite graphs

We begin the section by noting that the property of being {a, b}-weight colourable is not one that is inherited by subgraphs, nor is the property of being non-{a, b}-weight colourable. For example, the graph consisting of K 4 with a leaf attached is {1, 2}-weight colourable, however K 4 is not {a, b}-colourable for any choice of a and b. Similarly K 4 contains the subgraph C 4 which is 2-weight colourable. We can, however, characterize the minimal graphs with respect to subgraph containment in the class of graph which are not {a, b}-weight colourable for many pairs {a, b} (in particular, {1, 2}). In Theorem 3.9 we establish that any graph which is not {a, b}-weight colourable must contain C 2k+1 or C 4k+2 as a subgraph for some positive integer k.

Definition 3.1 A graph G is round if every cycle of G has length 0 mod 4.
The class of round graphs is much richer than merely those obtained by taking a graph and subdividing each edge into a path of length 4. For example, Θ (2,2,2) ∼ = K 2,3 is a round graph which is not obtained in this way.

The following lemma establishes a useful subgraph condition of round graphs which we will use in our study of the {a, b}-weight colourability of round graphs. Proposition 3.2 If G is a round graph and Θ (i,j,k) is a subgraph of G, then i, j and k are even and i ≡ j ≡ k (mod 4).

Proof: Let Θ (i,j,k) be a subgraph of G and let P i , P j and P k be the corresponding paths of length i, j and k respectively. Since G is round, i + j ≡ i + k ≡ j + k ≡ 0 (mod 4). The result follows.

2

Before proceeding with our results on bipartite graphs we present the following definition which we adopt throughout this section (and this section only). In any {a, b}-edge-weighting of a graph, the weighted degree of every vertex is of the form ra + sb for some nonnegative integers r, s. We will call a weighted vertex even (odd) if its weighted degree is ra + sb with r even (odd). Note that the parity of a weighted vertex does not necessarily refer to the parity of its weight. However, by Proposition 2.1, if a and b are not independent over Q then we will assume that they are relatively prime integers, and so we will assume that a is an odd integer in this case. If b is even, which will be the case in a number of the following results, then the parity of a weighted vertex does coincide with the parity of its weight.

Since a number of our arguments rely on this notion of parity, we often exclude those pairs of numbers whose ratio may be reduced to a ratio of odd integers. We define the sets:

E = {a, b} a b = p q , p, q odd integers N = {a, b} a b = p q , p, q ∈ Z, pq ≤ 0
We have already seen examples of bipartite graphs which are 2-weight colourable (C 4k for any k ≥ 1, bipartite theta graphs except Θ (1,4k2+1,...,4k d +1) ) and some which are not (C 4k+2 for any k ≥ 1). From these examples, we note that a bipartite graph G with both parts of odd size is not necessarily {a, b}weight colourable. However, if G has one part of even size, we are able to prove G is {a, b}-weight colourable for particular values of a and b.

Theorem 3.3 Let a, b ∈ R be such that {a, b} / ∈ E.
If G is a connected bipartite graph with at least one part being of even size, then G is {a, b}-weight colourable.

Proof: Let V (G) = X ∪ Y be a bipartition of the vertices of G with |X| even. By Corollary 2.2 and since {a, b} / ∈ E, we may assume that a is an odd integer and b is an even integer. We assign the weight b to each edge of G. Clearly v is even for each v ∈ V (G). Let V (X) = {x 1 , x 2 . . . x 2k } and let P i be an x 2i-1 x 2i -path in G. By changing every edge weight along P 1 we only change the parity of x 1 and x 2 . By repeating this process for each P i we have that every vertex of X has odd parity and every vertex of Y has even parity.

Call the resulting edge-weighting w. Suppose that w is not an {a, b}-weight colouring. Then there are adjacent vertices x and y such that w(x) = w(y). Thus there exist integers r, r , s, s such w(x) = ra+sb where r is odd, w(y) = r a + s b where r is even, and ra + sb = r a + s b. If a and b are linearly independent over Q, we must have r = r , a contradiction. Hence b = (p/q)a for some p, q ∈ Z with gcd(p, q) = 1. Thus rq + sp = r q + s p. Since r is odd and r is even, p even implies q must be even, a contradiction. Hence p is odd. Similarly, q is odd. Therefore, b/a = p/q with p, q odd, contradicting our choice of a and b. Thus w is an {a, b}-weight colouring of G. 2

Corollary 3.4 Let a, b ∈ R be such that {a, b} / ∈ E ∪N . Let G = K 2 be a connected bipartite graph with a vertex of degree 1. Then G is {a, b}-weight colourable. In particular, trees are {a, b}-weight colourable.

Proof: Let V (G) = X ∪ Y be a bipartition of the vertices of G. Let x ∈ X be a vertex of degree 1 and let y ∈ Y be its neighbour. If |X| or |Y | is even, then G is {a, b}-weight colourable by Theorem 3.3. If |X| is odd, then G -x has an {a, b}-weight colouring by Theorem 3.3, say w , such that vertices in X \ {x} are odd and vertices in Y are even. By assigning b to the edge xy we maintain the parity of all the vertices. Also, since {a, b} / ∈ N we have w (y) = 0 and so x and y will receive different weights, thus giving an {a, b}-weight colouring of G.

Theorem 3.5 Let a, b ∈ R be such that {a, b} / ∈ E ∪ N . Let G be a connected bipartite graph with a thread of even length P and let U be the internal vertices of P . If G -U is connected then G is {a, b}-weight colourable.

Proof: We may assume that a is a positive odd integer and b is a positive even integer. If X ∪ Y is the bipartition of V (G) and either |X| or |Y | is even, then G is {a, b}-weight colourable by Theorem 3.3. Assume both parts of G are of odd size. Let x and y be the ends of P . We first assume that x and y are distinct. By Lemma 2.8, we may assume that P is a path of length either 2 or 4.

Consider the case that P is of length 2, say P = xvy. Let G be the bipartite graph obtained from G by deleting v and adding two leaves, v 1 adjacent to x and v 2 adjacent to y. Now G is connected and bipartite with an even side, where v 1 and v 2 both belong to the even side. Theorem 3.3 gives an {a, b}-weight colouring of G , say w , so that v 1 and v 2 are both odd vertices. Hence xv 1 and yv 2 must both receive a as their weight. Let w be an {a, b}-edge-weighting of G, where w(xv) = w (xv 1 ) = a, w(yv) = w (yv 2 ) = a and w(e) = w (e) for all other edges e ∈ E(G). If w is not an {a, b}-weight colouring of G, then either w(x) = 2a or w(y) = 2a. Without loss of generality, suppose w(x) = ra + sb = 2a (a similar argument will hold for y). Since w(xv) = a and r even, we have r ≥ 2. If r = 2, then sb = 0 which implies s = 0 or equivalently deg G (x) = 2, a contradiction. If r ≥ 3, then sb < 0 which gives b < 0, a contradiction. Thus w is an {a, b}-weight colouring of G.

Suppose |P | = 4. Let P = xv 1 v 2 v 3 y and let G = G -v 2 . Now G is bipartite with an even side X , and x, y ∈ X . Theorem 3.3 gives an {a, b}-weight colouring of G , say w , so that v 1 and v 3 are both even vertices. Hence xv 1 and yv 3 must both receive b as their weight. Let w be an {a, b}-edge-weighting of G, where w(v 1 v 2 ) = w(v 2 v 3 ) = a and w(e) = w (e) for all other edges e ∈ E(G). If w is not an {a, b}-weight colouring of G, then either w(x) = a+b or w(y) = a+b. Suppose w(x) = ra+sb = a+b. Then (r -1)a = -(s -1)b, and thus r is odd. Again, we have that a and b are positive integers. Thus either r -1 < 0 or s -1 < 0. However, since w(xv 1 ) = b, we have s = 0, and since r is odd, r = 0. Thus w is an {a, b}-weight colouring of G. Now, suppose x and y are not distinct (call this vertex x). Then P is a cycle which is an end block of G and x is a cut vertex of G. Let z 1 and z 2 be the neighbours of x in P . Since G = G -U is a connected bipartite graph with one part having even size, then by Theorem 3.3 there is an {a, b}-weight colouring of G , say w . We give an edge weighting w of P as follows:

• if P has length 2 (mod 4), then by Proposition 2.12 we may define an {a, b}-weight colouring of P , w , so that w (z 1 ) = w (x) = w (z 2 ) = 2a and P is properly coloured elsewhere;

• if P has length 0 (mod 4), then by Proposition 2.9 we may define an {a, b}-weight colouring of P , w , so that w (x) is the larger of 2a and 2b and P is properly coloured.

Let w be the weighting obtained by combining w and w . Then w(x) > w(z 1 ), w(z 2 ) and x has the same parity under w as under w . Hence the weight of x is distinct from its neighbours in G. Since all other vertices are properly coloured by w or w , w gives an {a, b}-weight colouring of G. 2

Theorem 3.6 If G is a 2-connected round graph which is not a cycle then G contains at least 2 even ears.

Proof:

We first claim that G contains no proper 2-connected subgraph which contains all even ears of G. Toward a contradiction suppose H is a 2-connected maximal proper subgraph of G that contains all even ears of G. There exist two vertices of H, say x and y, which are connected by a path P such that H ∩ P = {x, y}. Since H is 2-connected, there are also 2 edge disjoint paths P and P in H between x and y. Thus P ∪ P ∪ P is a theta graph, and by Lemma 3.2 P must be of even length. Since H already contains all even ears of G, H = H ∪ P must be a proper subgraph of G but H is also 2-connected which contradicts the maximality of H. Now, if G has no even ear, then any cycle of G is a 2-connected subgraph containing all the even ears and this is a contradiction as G is not a cycle. If G has only one ear, let T be the ear and let x and y be the two ends of T . Then there are 2 edge disjoint paths connecting x and y, one of which must be edge disjoint from T . This path together with T forms a cycle that contains all the even ears of G, a contradiction. 2

Corollary 3.7 If G is a round graph and all threads of G are odd, then G has at least two leaves.

We are now able to prove that round graphs can be edge-weight vertex-coloured with most sets of size 2.

Theorem 3.8 Every round graph is {a, b}-weight colourable for {a, b} / ∈ E ∪ N .

Proof: Let G be a round graph. Let B be an end block with vertex of attachment v. If B is isomorphic to K 2 , then G is a bipartite graph with a leaf and thus is {a, b}-weight colourable by Corollary 3.4. If B is a cycle, then B is an even thread and G is {a, b}-weight colourable by Theorem 3.5. Otherwise, if B is a 2-connected graph which is not a cycle, then by Theorem 3.6, B has at least two even ears and thus B has at least one even ear, say P , which does not contain v as an internal vertex. Let U be the internal vertices of P . Since G -U is connected, G is {a, b}-weight colourable by Theorem 3.5. 2

Theorem 3.8, together with Proposition 2.9, gives a class of minimal subgraphs with respect to containment which cannot be {a, b}-weight coloured for the pairs {a, b} on which we have focused.

Corollary 3.9 Let a and b be real numbers such that {a, b} / ∈ E ∪ N . Any graph which is not {a, b}weight colourable must contain a cycle of length 1, 2 or 3 mod 4.

We end this section with the following problem.

Problem 3 Is it true that all bipartite graphs except C 4k+2 and Θ (1,4k1+1,4k2+1,...,4k d +1) are 2-weight colourable?

4 More families of graphs with determined 2-weight colourability

We have given a number of examples of {a, b}-weight colourable graphs for values of a and b subject to particular restrictions. However we have seen few examples of graphs for which a and b can be any distinct real numbers. We note that the Petersen graph provides such an example of a 2-weight colourable graph. One such edge-weighting is given in Figure 1. By Proposition 2.3, note that any 2-weight colouring of the Petersen graph gives a 3-colouring of it, which is also an optimal proper vertex colouring.

In the rest of this section we describe more families of 2-weight colourable graphs as well as a class of nonbipartite graphs which are {a, b}-weight colourable when ab > 0. In particular we show that all unicyclic graphs except cycles of length 1, 2, 3 mod 4 are 2-weight colourable. We also provide a number of results on Cartesian products of graphs. Finally, we explore techniques for constructing graphs which do not admit {a, b}-weight colourings for any choice of a and b.

We begin with our result on unicyclic graphs.

Theorem 4.1 Every connected unicyclic graph except C 2k+1 and C 4m+2 is {a, b}-weight colourable, where a and b are real numbers with ab > 0.

Proof: We may assume that 0 < a < b. By contradiction, let G be the smallest counterexample to our claim. Let C be the only cycle of G. We first note that by Lemma 2.6, we may assume that every vertex of G is either on C or is adjacent to a vertex of C. We may also assume that every vertex of G has degree at most 3. Next, we claim that there are at least two vertices of degree at least 3 on C. If not, let v be the only vertex of degree at least 3 on C. Let x and y be the neighbours of v on C. It is easy to find an edge-weighting w of C which yields a proper colouring on C -v and w(v) ≥ w(x), w(y). By assigning b to the other edge incident with v, we get an {a, b}-weight colouring of G, a contradiction. Next, we claim that G has at most one ear of length at least 2. If not, then we choose some maximal path of degree 3 vertices on C, x 1 , . . . , x k , and remove all leaves of G adjacent to those vertices. Call this subgraph G . By minimality of our choice of G, we can assign an {a, b}-weight colouring w to G . Let w be the weighting of E(G) given by w(e) = w (e) if e ∈ E(G ) and w(e) = b otherwise. The only possible conflicts are between x 1 and its neighbour on C which is not x 2 , say y (or, similarly, between x k and it's neighbour on C which is not x k-1 ). However, since w(x 1 ) ≥ a + b + w(x 1 y) and w(y) ≤ w(x 1 y) + b (similar for x k ), w is an {a, b}-weight colouring of G which contradicts our choice of G.

If G has exactly one ear of length at least 2, let e = rs and e = r s be the two edges that have exactly one endpoint of degree 2. Specifically, let deg(r) = deg(r ) = 2, deg(s) = deg(s ) = 3. Note that r and r need not be distinct, but, since there are at least 2 vertices on C of degree 3, s and s are distinct. We construct an {a, b}-weight colouring of G based on the length of C mod 4. Clearly each leaf's neighbour has a weight strictly greater than its own. Since w gives a proper colouring of C except for r and s, the only adjacent vertices of G which might not be properly coloured are r and s or r and s . However, our choice of weights for the leaves of G guarantees that r, s, r , s are properly coloured as well. Thus w is an {a, b}-weight colouring of G.

• Suppose |C| ≡ 0 (mod 4). By Proposition 2.9, and so w is an {a, b}-weight colouring of G.

C
The only remaining case is that every vertex of C has degree 3. If |C| is even, assign the same weight to all the edges on the cycle and alternating weights to the leaf edges. The reader can verify that a solution for the cases when |C| = 3 or |C| = 5 exists. Each of these cases can be extended to larger odd cycle by making the replacement indicated in Figure 2. Note that the variables ¯ and n refer to the weights different from and n, respectively. Thus, no minimal counterexample G exists. 2 Proposition 4.2 For n ≥ 4, the graph K 2 2 K n is 2-weight colourable.

Proof: Let K n and K n be the two copies of the complete graph. Denote the vertices of K n and K n , respectively by

{u 1 , u 2 , . . . , u n/2 , v n/2 , v n/2 +1 , . . . , v n-2 , v n-1 }, {u 1 , u 2 , . . . , u n/2 , v n/2 , v n/2 +1 , . . . , v n-2 , v n-1 }.
Let p be a derangement (permutation with no fixed points) of {1, n/2 } and π be a derangement of { n/2 , n -1}. Let u i be adjacent to u p(i) for all 1 ≤ i ≤ n/2 and v i be adjacent to v π(i) for n/2 ≤ i ≤ n -1.

Since the graph is n-regular, if adjacent vertices have distinct weights then they have distinct numbers of incident edges having weight b. Using Lemma 2.5, we may weight the edges of K n and K n so that the subscript of the vertex is precisely equal to the number of edges weighted b incident to that edge in K n . Label u i u p(i) with a for all 1 ≤ i ≤ n/2 and weight v i v π(i) with b for n/2 ≤ i ≤ n -1. Then any two vertices that are adjacent have a distinct number of incident edges weighted b and thus K 2 2 K n is 2-weight colourable.

2

Figure 3 gives an illustration of this construction. Proof: If n is even, then give every edge of one copy of C n weight a and every edge of the other copy weight b. By alternating the weights of the images of K 2 between a and b along the cycles, we have the desired {a, b}-weight colouring. An example of an {a, b}-weight colouring of K 2 2 C 7 is given in Figure 4. It can be extended to an {a, b}-weight colouring of K 2 2 C 9 by replacing the left subgraph in Figure 5 with the right graph. Note that the right subgraph contains the left one, and thus this operation may be repeated as many times as needed to give an {a, b}-weight colouring for any K 2 2 C 2k+1 (k ≥ 3) The reader may verify that no {a, b}-weight colouring of K 2 2 C 3 or K 2 2 C 5 exists. 2

K n u 1 v [ n 2 ] v [ n 2 ] K n v n-1 u 1 • • • • • • v n-1 u [ n 2 ] • • • u [ n 2 • • •
Theorem 4.4 Let G be a graph and H be a regular bipartite graph.

If G 2 K 2 is 2-weight colourable, then G 2 H is 2-weight colourable.
Proof: Let w be an {a, b}-weight colouring of G 2 K 2 . Denote the two copies of G by G 1 and G 2 and denote the vertices of K 2 by t 1 and t 2 . Since H is regular (say d-regular) and bipartite, Hall's Theorem guarantees a perfect matching M of H. Let X and Y be the parts of V (H). Define an edge-weighting of G 2 H as follows. For each edge e = xy ∈ M where x ∈ X and y ∈ Y , weight the edges of the subgraph G 2 e by w so that each vertex (u G , x) ∈ V (G 2 H) has weight w(u G , t 1 ) and (u G , y) ∈ V (G 2 H) has weight w(u G , t 2 ). Assign every other edge of G 2 H weight a. Call this weighting φ.

We have that φ

(u) = w(u G , t 1 ) + (d -1)a if u H ∈ X and φ(u) = w(u G , t 2 ) + (d -1)a if u H ∈ Y .
Two vertices are adjacent if either their H-coordinates agree and they are adjacent in a copy of G or if their G-coordinates agree and they are adjacent in a copy of H. In the former case, their weights are distinct under φ since they are distinct under w. In the latter, consider two adjacent vertices u = (u G , u H ) and u

= (u G , u H ) where u H ∈ X, u H ∈ Y . Then, w(u G , t 1 ) = w(u G , t 2 ) by choice of w, which implies that φ(u) = φ(u ). Thus φ is an {a, b}-weight colouring of G 2 H. 2
Corollary 4.5 If G and H are regular bipartite graphs, then the following graphs are 2-weight colourable:

(i) K n 2 H, if n ≥ 4 (ii) C n 2 H if n ≥ 4, n = 5 (iii) G 2 H
An example is given on the left of Figure 6. In the case G = K 2 and n = 4, the weight of the leaf's edge is forced to be equal to that of its incident edges; this is another useful gadget. It is shown on the right of Figure 6. (i) Join two copies of K4 by an edge attached at their vertices of degree 2.

(ii) Join 2n + 1 copies of K4 to a C 2n+1 by an edge attaching the degree 2 vertex in each copy of K4 to a distinct cycle vertex.

To see why the graph defined in (ii), which we denote H, cannot be S-weight coloured for any set S of size 2, consider the accumulated weight at one of the cycle vertices, say v. Since H is 3-regular graph, w(v) ∈ {3a, 2a+b, a+2b, 3b}. If w(v) = 3a, then the noncycle edge, e, incident with v must have weight a and, as shown in Figure 6, so must the two edges in the copy of K4 joined to v by an edge. Thus both endpoints of e would have weight 3a. A similar argument shows that w(v) = 3b. Thus the only possible accumulated weights on cycle vertices are 2a + b and 2b + a. Since an odd cycle cannot be properly 2-coloured, we see that H cannot be 2-weight coloured.

Our next family of gadget graphs are described below.

Proposition 4.9 Let 0 ≤ a ∈ Z and d | a. Let H be a graph and G be a graph obtained from identifying a vertex u of H with a vertex of a K n (all other vertices of H and K n being disjoint). If Proof: We first prove the statement for d = 1. Toward a contradiction, suppose w is an {a, a + 1}weighting colouring of G. Every vertex of K n -u has weighted degree ra + (n -1 -r)(a + 1) = (n -1)(a + 1) -r for some 0 ≤ r ≤ n -1 and both of the weights (n -1)a and (n -1)(a + 1) cannot appear simultaneously on K n -u. If w(u) < (n -1)(a + 1) then there are only n -1 colours available for the vertices of K n , a contradiction. So w(u) ≥ (n -1)(a + 1). Let w| Kn be the edge-weighting of K n induced by w. By Corollary 2.4, K n is not {a, a + 1}-edgeweight colourable. Thus, there must be exactly two vertices of K n with the same weight given by w| Kn and u must be one such vertex. By Lemma 2.5, we get w| Kn (u) = ra + (n -1 -r)(a + 1) = (n -1)(a + 1) -r, where r ∈ { n/2 , n/2 -1}. Note that r ≥ (n -1)/2 . If u is incident with s edges of weight a in H, then we have (n -1)(a + 1) ≤ w(u) = ra + (n -1 -r)(a + 1) + sa + (deg H (u) -s)(a + 1), We may use Proposition 4.9 to construct many graphs which are not {a, a + 1}-weight colourable and so, in particular, are not {1, 2}-weight colourable. In fact, if H is any graph and u any vertex of H, then there is an n large enough so that attaching K n to u (and only to u) gives a graph which is not {a, a + 1}weight colourable. We can also use the equality condition to construct graphs with no {a, a + 1}-weight colouring (for a specific a). For example, the graph obtained by joining two copies of K n , n ≥ 5, with a path of length 3, say e 1 , e 2 , e 3 , is not {a, a + 1}-weight colourable for a = n-1 2 -1 since the weights of e 1 and e 3 are forced to be a + 1, and thus the ends of e 2 will receive the same weight.

which
We finish this section with a problem whose solution would be useful in the study of {1, 2, 3}-weight colourable graphs.

Problem 4 Does there exist a graph which is either • uniquely {1, 2, 3}-weight colourable (up to isomorphism), or • {1, 2, 3}-weight colourable where any such colouring forces certain edges of G to receive a particular weight?

Moreover, does there exist a graph with either of these properties which maintains that property when it is attached in some way to another graph?

  1 and b = -a (case iv. below). The neighbours of x have accumulated weights either a + b or 2a. If w(x) = (d -1)a + b = a + b then this implies that d = 2 but the hypotheses of the theorem include d ≥ 3. If w(x) = (d -1)a + b = 2a then b = -(d -3)a. The fact that d ≥ 3 and |a| ≥ |b| now give either

Fig. 1 :

 1 Fig. 1: An {a, b}-weight colouring of the Petersen graph. Bold edges are to receive weight b.

•

  Suppose |C| is odd. By Proposition 2.10, C has an {a, b}-edge weighting w which gives a proper vertex colouring except across rs. Let w(e) = w (e) if e ∈ E(C). If w (r ) -w (s ) = a, let w(e) = b for all e ∈ E(G) \ E(C). Otherwise, let w(e) = a for all e ∈ E(G) \ E(C).

  has an {a, b}-weight colouring w such that w(r) = 2a and w(s) = a + b. Let w(e) = w (e) if e ∈ E(C). If w (r ) -w (s ) = a, let w(e) = b for all e ∈ E(G) \ E(C). Otherwise, let w(e) = a for all e ∈ E(G) \ E(C). By the same argument as above, w is an {a, b}-weight colouring of G. • Suppose |C| ≡ 2 (mod 4). Let t be the other neighbour of s on C and let t be the other neighbour of r on C. By Proposition 2.11, there is an {a, b}-edge weighting such that all vertices are properly coloured except r, s and t, and such that w(t r ) = w(r s ) = a. Let w(e) = w (e) for all e ∈ E(C). Let f be the edge between s and its leaf, and let w(f ) = a. For each e ∈ E(G)\E(C)\{f }, let w(e) = b. The only possible improperly coloured pairs of vertices are r and s, s and t or r and s . However, w(r) = w (r) = w (s) < w(s) w(s) = w (s) + a = w (t) + a < w (t) + b = w(t) w(r ) = 2a < a + 2b = w(s )

Fig. 2 :

 2 Fig. 2: Replacement operation to expand 2-weight colourings to larger cycles.

Fig. 3 :

 3 Fig. 3: An {a, b}-weight colouring of K2 2 Kn. Bold edges are to receive weight b.

Fig. 4 :

 4 Fig. 4: An {a, b}-weight colouring of K2 2 C7. Bold edges are to receive weight b.

Fig. 5 :

 5 Fig. 5: Replacement operation for obtaining an {a, b}-weight colouring of K2 2 C 2k+1 for k ≥ 4.

Fig. 6 :

 6 Fig. 6: The graphs K4 and K4 with a leaf are 2-weight colourable. Bold edges represent one weight-class. We use Proposition 4.6, which established the weight colourability of Kn , to construct the following examples of non 2-weight colourable graphs. Example 4.8 The following graphs cannot be 2-weight coloured:

  G is not {a, a + d}-weight colourable. Furthermore, if deg H (u) = d a + d n -1 2 ,then in any {a, a + d}-weight colouring of G, all edges in H incident to u must receive weight a + d.

  simplifies to deg H (u) ≥ ( 1 a+1 )(r + s). Hence = 0, proving the second claim. Now, let d be any positive divisor of a. By Proposition 2.1, G has an {a, a + d}-weight colouring if and only if it has a a d , a d + 1 -weight colouring. If deg H (u) < -weight colouring by the above argument. Hence, if deg H (u) < ( d a+d ) n-1 2 then G has no {a, a + d}-weight colouring. The second result follows similarly. 2

	deg H (u) ≥	1 a + 1	n -1 2	+ s .
	This is a contradiction since deg H (u) < ( 1 a+1 ) n-1 2	. Also, if deg H (u) = ( 1 a+1 ) n-1 2	then we must
	have s 1 a/d+1	n-1 2	then G has no
	a d , a d + 1

* Partially supported by NSERC Canada. † Partially supported by Fonds québécois de la recherche sur la nature et les technologies.

Proof: Applying Theorem 4.4 to Propositions 4.2 and 4.3 immediately gives results (i) and (ii) respectively. For (iii), since K 2 2 K 2 ∼ = C 4 , K 2 2 K 2 is 2-weight colourable by Proposition 2.9. By Theorem 4.4, K 2 2 H is 2-weight colourable; applying Theorem 4.4 again gives us that G 2 H is 2-weight colourable.

2

In order to construct non-2-weight colourable graphs below, we make use of a class of "gadget" graphs. These gadgets are themselves 2-weight colourable, but they have the property that in any of their 2-weight colourings, certain edges receive a predetermined weight.

Define the graph K n to be the graph obtained from K n by subdividing one edge exactly once.

Proposition 4.6 For n ≥ 4, the graph K n is 2-weight colourable. Moreover, in any 2-weight colouring of K n , the edges incident to its degree 2 vertex must receive the same colour.

Proof: Let x be the vertex of K n of degree 2 and let u, v be its neighbours. An {a, b}-weight colouring of K 4 is given in Figure 6. So assume n ≥ 5. Let K n be obtained by adding the edge uv to K n -x. By Lemma 2.5, there exists an edge-weighting w of K n such that all the vertices have distinct weighted degrees except for u and v. Moreover,

Assign the weight w(uv) from K n to the edges xu and xv in K n . Note that w is an {a, b}-weight colouring as long as w(u) = w(v) = w(x). We have w(x) ∈ {2a, 2b}. Since a and b may be swapped in Lemma 2.5, we assume that w(x) = 2a. If w(u) = 2a, we are done. Suppose w(u) = 2a. We consider two cases:

• If n is odd, then the edge weighting w given by swapping every edge's weight gives w (u) = w(u) = 2a = 2b = w (x).

• If n is even then, by the construction of the weighting in Lemma 2.5, w(u)

If the edge weighting w given by swapping every edge's weight gives a conflict between u and x, then 2b = n 2 (a + b) -a. Together, these imply that a = b, a contradiction.

Thus K n admits an {a, b}-weight colouring.

To prove the second part, toward a contradiction, suppose K n is the smallest counterexample for which there exists an {a, b}-weight colouring w such that w(xu) = w(xv). By inspection, we may check that K 4 does not admit such edge-weighting. So assume n ≥ 5. Note that there exists no vertex y = u, v such that w(y) ∈ {(n -1)a, (n -1)b}, otherwise K n -y would be a smaller counterexample. Therefore, since w induces a vertex colouring and all the weighted degrees (except for x) are of the form ra + (n -1 -r)b for some 0 ≤ r ≤ n -1, we must have w(u), w(v) ∈ {(n -1)a, (n -1)b}. But then by removing u, v, and x we get an {a, b}-weight colouring of K n-2 , a contradiction to Corollary 2.4. 2

Corollary 4.7 Given a graph G, let G be obtained from identifying a vertex of G with the degree 2 vertex of K n . Then in any 2-weight colouring of G , edges in Kn incident to its degree 2 vertex must receive same colour.

Proof: Since the proof of Proposition 4.6 did not depend in any way on the accumulated weight at vertex x, then regardless of graph joined to Kn at x, the two edges incident with x in Kn must still receive the same weight. 2