P Mark Kayll
email: mark.kayll@umontana.edu

Well-spread sequences and edge-labellings with constant Hamilton-weight

Keywords: Well-spread, weak Sidon, graph labelling, Hamilton cycle

A sequence (a i ) of integers is well-spread if the sums a i + a j , for i < j, are all different. For a fixed positive integer r, let W r (N) denote the maximum integer n for which there exists a well-spread sequence 0 ≤ a 1 < • • • < a n ≤ N with a i ≡ a j ( mod r) for all i, j. We give a new proof that W r (N) < (N/r) 1/2 + O((N/r) 1/4 ); our approach improves a bound of Ruzsa [Acta. Arith. 65 (1993), 259-283] by decreasing the implicit constant, essentially from 4 to √ 3. We apply this result to verify a conjecture of Jones et al. from [Discuss. Math. Graph Theory 23 (2003), 287-307]. The application concerns the growth-rate of the maximum label Λ(n) in a 'most-efficient' metric, injective edgelabelling of K n with the property that every Hamilton cycle has the same length; we prove that 2n 2 -O(n 3/2 ) < Λ(n) < 2n 2 + O(n 61/40 ).

Introduction

Ostensibly our purpose is to prove a conjecture from [START_REF] Jones | On constant-weight TSP-tours[END_REF] concerning the growth-rate of the maximum label in a certain edge-labelling of K n . The essential ingredient in the proof, Theorem 4, determines asymptotically the maximum 'density' of a finite, well-spread sequence of nonnegative integers. This result was first proved (explicitly) by Ruzsa [START_REF] Ruzsa | Solving a linear equation in a set of integers I[END_REF]; our proof improves upon his bound and as such may be of independent interest.

Sets and sequences

We write Z + and N, respectively, for the sets of positive and nonnegative integers. Kotzig [START_REF] Kotzig | On well spread sets of integers[END_REF] called a sequence (a i ) of integers well-spread if the sums a i + a j , for i < j, are all different; weak Sidon is used synonymously, e.g., in [START_REF] Ruzsa | Solving a linear equation in a set of integers I[END_REF]. He studied finite, well-spread sequences in part due to their relationship with 'magic valuations'-now called 'edge-magic total labellings'-of graphs; see [START_REF] Phillips | Well-spread sequences (Papers in honour of Stephen T. Hedetniemi)[END_REF] for further details. If we strengthen the condition and require that all the sums a i + a j , for i ≤ j, be distinct, then (a i ) is called a Sidon sequence. In connection with his studies in Fourier theory, Sidon [START_REF] Sidon | Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen[END_REF][START_REF]Über die Fourier Konstanten der Functionen der Klasse L p für p > 1[END_REF] considered these sequences under the name B 2 -sequence; see [START_REF] Halberstam | Sequences[END_REF] for a basic reference. Every Sidon sequence is well-spread, but it is easy to construct examples to show that the converse is false: e.g., (1, 2, 3). We shall fix a modulus r ∈ Z + and consider constant-residue integral sequences (a i ), i.e., ones 1365-8050 c 2004 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France for which a i ≡ a j ( mod r) for all i, j; our application depends on the case r = 2, viz., the constant-parity sequences.

Our main number-theoretic contribution (Theorem 4) concerns the asymptotic behaviour of the following functions from N onto Z + :

W (N) := max{n : there is a well-spread sequence 0 ≤ a 1 < • • • < a n ≤ N}; W r (N) := max{n : there is a constant-residue, well-spread sequence 0 ≤ a 1 < • • • < a n ≤ N}.
We use S, S r , respectively, for the functions defined by replacing 'well-spread' by 'Sidon' in these definitions. Several basic inequalities follow at once:

S r (N) ≤ W r (N), S(N) ≤ W (N) for each N ∈ N.
(1)

Since the well-spread and Sidon properties are invariant under (integral) affine transformations, the maximum length of either type of sequence contained in an (N + 1)-term arithmetic progression is the same as among an initial segment of N + 1 nonnegative integers. Thus,

S r (N) = S N r and W r (N) = W N r . (2)
Though we need only W 2 for our graph labelling application, we shall state our number-theoretic results in terms of W r since we prefer to display explicitly the dependence on the modulus r.

Graphs and labellings

Since we employ standard graph-theoretic notation, we refer the reader to any basic text-e.g. [Wes01]for omitted definitions. We use [n] := {1, . . . , n} for the vertex set of a complete graph K n . If A is an edge with ends i, j, then we write A = i j. An edge-labelling of K n is a function λ : E(K n ) → Z + . We say that λ has constant Hamilton-weight whenever the value of ∑ A∈E(H) λ(A) is independent of the Hamilton cycle H, and is metric if it satisfies the triangle-inequality: λ(ik) ≤ λ(i j) + λ( jk) for every triple i, j, k ∈ [n].

Our main graph-theoretic contribution (Theorem 6) verifies a conjecture from [START_REF] Jones | On constant-weight TSP-tours[END_REF] by determining the asymptotic growth-rate of the following function from Z + into Z + :

Λ(n) := min λ max A∈E(K n ) λ(A),
the minimum being taken over all metric, injective edge-labellings λ of K n having constant Hamiltonweight.

Background

Let us begin with a celebrated result of Erdős and others on the 'density' of finite Sidon sequences. Here and throughout this paper, all asymptotic assertions are contingent on the relevant parameter (N or n) tending to infinity.

Theorem 1 S(N) ∼ N 1/2 ; i.e., 1 -o(1) N 1/2 < S(N) < 1 + o(1) N 1/2 .
(3)

The upper bound in (3)-in the form N 1/2 + O(N 1/4 )-was proved by Erdős and Turán [START_REF] Erdős | On a problem of Sidon in additive number theory, and on some related problems[END_REF], who also established the lower bound (1/ √ 2o(1))N 1/2 ; later Chowla [START_REF] Chowla | Solution of a problem of Erdős and Turán in additive-number theory[END_REF][START_REF]Solution of a problem of Erdős and Turán in additive-number-theory[END_REF] and independently Erdős (1944, unpublished) applied a result of Singer [START_REF] Singer | A theorem in finite projective geometry and some applications to number theory[END_REF] (Theorem 5 below) to improve the lower bound to that in (3). Bose and Chowla [START_REF] Bose | Theorems in the additive theory of numbers[END_REF] proved a generalization of (3) to 'B r -sequences'; this reference also provides a more accessible discussion of Chowla's result. Eventually Lindström [START_REF] Lindström | An inequality for B 2 -sequences[END_REF] improved the upper bound to N 1/2 + N 1/4 + O(1). It remains open-and was given a price tag by Erdősto decide whether, for every ε > 0, the inequality S(N) < N 1/2 + o(N ε ) holds. See [START_REF] Babai | Sidon sets in groups and induced subgraphs of Cayley graphs[END_REF][START_REF] Sós | An additive problem in different structures, Graph theory, combinatorics, algorithms, and applications[END_REF] for further discussion and references. See [AKS81, Guy94, Ruz98, Sid32, Sid35] for a precise statement and related progress on the corresponding infinite problem.

The following theorem from [START_REF] Jones | On constant-weight TSP-tours[END_REF] provides a connection between sequences and labellings; see also [START_REF] Kabadi | Weighted graphs with all Hamiltonian cycles of the same length[END_REF] and the references therein for antecedents of this result.

Theorem 2 For n ≥ 3, a metric, injective edge-labelling λ of K n has constant Hamilton-weight if and only if there is a constant-parity, well-spread N-sequence (a i ) n i=1 such that

λ(i j) = a i + a j 2 for each edge i j of K n .
The sequence (a i ) is uniquely determined by λ.

Theorem 2 shows that if we define ψ cp : Z + → N by

ψ cp (n) := min{a n-1 + a n : there exists a constant-parity, well-spread N-sequence a 1 < • • • < a n }, then Λ(n) = ψ cp (n) 2 for every n ≥ 3. (4)
We note in passing that for finite Sidon sequences (a i ), similar 'sum-sets' {a i + a j | i ≤ j} have been investigated considerably; see [START_REF]Sumsets of Sidon sets[END_REF] for recent results and further references. For our study of Λ, we additionally introduce the function σ cp : Z + → N, defined by σ cp (n) := min{a n : there exists a constant-parity, well-spread N-sequence

a 1 < • • • < a n }.

Packing with 2-sums

The definition of ψ cp exhibits a 'packing flavour'; indeed, a variant of ψ cp using this terminology was studied by Graham and Sloane [START_REF] Graham | On additive bases and harmonious graphs[END_REF]. They defined v α (n) to be the smallest nonnegative integer N such that there exists an integral sequence 0 = a 1 < • • • < a n with the property that the sums a i + a j , for i < j, belong to [0, N] and represent each element of this set at most once. If ψ denotes our ψ cp without the constant-parity condition, then ψ = v α . Graham and Sloane tabulated the values v α (n) for n ≤ 10, gave exemplary sequences, and outlined a proof of

2n 2 -O(n 3/2 ) < v α (n) < 2n 2 + O(n 36/23 ). (5)
They also considered the three functions that arise when i < j is changed to i ≤ j (giving the Sidon version of v α ) or when the arithmetic is done modulo N, and the four functions resulting from changing smallest to largest and at most to at least (giving the covering analogues of the four packing functions). By now these eight functions enjoy a vast literature, much of which was cited already in [START_REF] Graham | On additive bases and harmonious graphs[END_REF]. After proving our main graph-theoretic result (Theorem 6), we shall indicate a slight improvement to the upper bound in (5). Similar improvements are possible in the bounds for the other packing functions.

2 Well-spread sequences Theorem 1 and (2) show that S r (N) ∼ (N/r) 1/2 . The functions W r exhibit the same asymptotic behaviour, since Ruzsa [START_REF] Ruzsa | Solving a linear equation in a set of integers I[END_REF] proved that a well-spread sequence contained in the set {1, . . . , N} contains at most N 1/2 + 4N 1/4 + 11 terms. An upper bound for W (N) of the form N 1/2 + O(N 1/4 ) is also implicit in the work of Graham and Sloane [START_REF] Graham | On additive bases and harmonious graphs[END_REF] and was probably known to these authors. Presently, we shall derive this result again, in terms of W r .

To get started, we need a cruder estimate:

Lemma 3 If N is sufficiently large, then W r (N) < 2.001(N/r) 1/2 . Proof. Let n = W r (N) and 0 ≤ a 1 < • • • < a n
≤ N be a well-spread sequence with each a i ≡ k ( mod r), for some 0 ≤ k < r. The sums a i + a j , for i < j, are distinct, at most 2Nr, congruent modulo r to 2k, and hence lie in the set {2k + r, 2k + 2r, . . . , 2k + ℓr}, where ℓ := ⌊(2Nr -2k)/r⌋. Thus n 2 ≤ ℓ, from which n < (2ℓ) 1/2 + 1, and hence the assertion, follow easily.

✷

Theorem 4 W r (N) < (N/r) 1/2 + O((N/r) 1/4 ).
Proof. Let N be large enough to invoke Lemma 3, and set n :=W r (N). Then there exists a constant-residue, well-spread sequence 0

≤ a 1 < • • • < a n ≤ N.
For 1 ≤ i < j ≤ n, Lindström [Lin69] called ji the order of the difference a ja i . He observed that the differences of order ν > 0 can be arranged into sequences of the form

a α -a β , a β -a γ , a γ -a δ , . . . , where α -β = β -γ = γ -δ = • • • = ν.
Because of 'telescoping', the sum of all these differences is at most νN (and less than νN for ν > 1). Thus, for m ≥ 2, the sum S of all the positive differences of order at most m is less than m(m + 1)N/2.

Let us call a i a mean-point if 2a i = a j + a k for some j, k ∈ [n]; notice that in this case a ia k = a ja i . Except for the values a ja i , for mean points a i (or a j ), the differences a ka ℓ , for 1 ≤ ℓ < k ≤ n, are all different since (a i ) is well-spread. As the only candidates for mean-points are a 2 , . . . , a n-1 , we have at most t := n -2 differences occurring with higher multiplicity, and the well-spread property implies that this multiplicity is 2. Since (a i ) has constant-residue, the differences are all multiples of r. If 1 ≤ m < n and s := n -(m + 1)/2, then the number of positive differences of order at most m is mnm(m + 1)/2 = ms. Therefore,

S ≥ t ∑ i=1 (ri + ri) + ms-2t ∑ j=1 (rt + r j) = rms(ms + 1) 2 -rt(ms -t).
For 1 < m < n, it follows that

rms(ms + 1) 2 -rt(ms -t) < m(m + 1) 2 N, so that r(ms) 2 2 < m(m + 1) 2 N + rmst.
Since s,t < n, the second term on the right side is less than rmn 2 , which by Lemma 3 is at most (2.001) 2 mN < 4.5mN. Thus, s 2 < N(1 + 10/m)/r, and since (1 + x) 1/2 < 1 + x/2 for x = 10/m, we have

n = m + 1 2 + s < m + 1 2 + N r 1/2 1 + 5 m . (6)
With m := ⌈(N/r) 1/4 ⌉, this gives the bound in the statement of the theorem. ✷ Remarks Our proof of Theorem 4 adapts the main idea of Lindström [START_REF] Lindström | An inequality for B 2 -sequences[END_REF] to well-spread, constantresidue sequences. Ruzsa [START_REF] Ruzsa | Solving a linear equation in a set of integers I[END_REF] also based his proof on the idea of studying the 'small' differences a ja i , though in a "somewhat hidden" fashion (quote from [START_REF] Ruzsa | Solving a linear equation in a set of integers I[END_REF]). Here we compare the resulting implicit constants.

To optimize ours, we iterate the proof once again. Instead of applying Lemma 3 (to bound rmn 2 from above), we apply Theorem 4 itself. This allows us to replace '10' by '3 + O((N/r) -1/4 )'. To minimize the right side of (the adjusted) inequality (6), we now choose m to be ⌈ √ 3(N/r) 1/4 ⌉. These modifications replace the big-oh term in Theorem 4 by √ 3(N/r) 1/4 + O(1). Ruzsa's proof essentially produces the value 4 in place of our √ 3. While we're comparing bounds, we should mention that the upper bound for S r (N) implied by (1) and Theorem 4 does not improve on earlier results. For example, Lindström's bound [START_REF] Lindström | An inequality for B 2 -sequences[END_REF] together with (2) gives the implied constant 1 in place of our √ 3 ✷

Edge-labellings with constant Hamilton-weight

We turn to verifying the main conjecture from [START_REF] Jones | On constant-weight TSP-tours[END_REF]. Proofs of the following basic connections are left to the reader (or see [START_REF] Jones | On constant-weight TSP-tours[END_REF]):

W 2 (N) ≥ σ -1 cp (N) for every N ∈ range(σ cp );

ψ cp (n) ≥ σ cp (n) + σ cp (n -1) for every n ≥ 2. (8)

We also need a simple upper bound on σ cp (n), a theorem on the density of primes, and Singer's theorem on difference sets. The first of these follows immediately from our work in [START_REF] Jones | On constant-weight TSP-tours[END_REF]:

σ cp (n) < 2n 2 (1 + o(1)). ( 9
)
For the second, we opt for the present state-of-the-art, due to Baker et al. [START_REF] Baker | The difference between consecutive primes, II[END_REF]: if x is sufficiently large, then there is a prime p with x < p ≤ x + x 21/40 . (10)

For the third, we have Theorem 5 ([Sin38]) If q is a prime power, then there are integers b 0 , b 1 , . . . , b q ∈ [0, q 2 + q] such that the differences b ib j , for i = j, are congruent, modulo q 2 + q + 1, to the integers 1, 2, . . . , q 2 + q. In particular, (b i ) q i=0 forms a Sidon sequence, hence is well-spread. Finally, we state and prove our main graph-theoretic result: Theorem 6 Λ(n) ∼ 2n 2 ; more precisely, 2n 2 -O(n 3/2 ) < Λ(n) < 2n 2 + O(n 61/40 ).

(11)

Acknowledgements

This paper's first draft was written during my sabbatical leave at the University of Ljubljana, Slovenia. Thanks to the Department of Mathematics, the Institute of Mathematics, Physics & Mechanics, and especially to Bojan Mohar for their hospitality. I am grateful to a referee for the reference [Ruz93] and for pointing out the relations in (2).

Proof. For the upper bound, consider an integer n, large enough to apply (10) with x = n -1; then we can find a prime p so that n -1 < p < n + n 21/40 .

Theorem 5 delivers a well-spread sequence 0

. . , n, defines a constant-parity, well-spread sequence with

By definition, ψ cp (n) ≤ a n-1 + a n , and since Λ(n) = ψ cp (n)/2 (see (4)), the upper bound in (11) follows.

For the lower bound, let n ∈ N and N = σ cp (n). Then (7) and Theorem 4 imply that

Thus (8) gives ψ cp (n) > 4n 2 -O(n 3/2 ), and again applying (4) yields the desired bound. ✷

Closing remarks

We first elaborate on the lower bound in (3). The idea in the proof of the upper bound in Theorem 6 can be used to show that S r (N) > (N/r) 1/2 for infinitely many integers N and that S r (N) > (N/r) 1/2 -(N/r) 21/80 for sufficiently large N. Absent the modulus r, these observations have been made elsewhere; cf. [START_REF] Pomerance | Combinatorial number theory, Handbook of Combinatorics[END_REF]. The slight improvement here over previously published bounds-e.g., in [START_REF] Pomerance | Combinatorial number theory, Handbook of Combinatorics[END_REF], the fraction 5/16 replaces 21/80-results from our use of a more recent prime density theorem. Baker and Harman [START_REF] Baker | The difference between consecutive primes[END_REF] sketch the history of such theorems, i.e., those of the form [x, x + x ϑ ] contains a prime whenever x is sufficiently large for a specified constant ϑ; cf. ( 10).

An alternate approach to Theorem 6 is to reduce the problem to one considered in [START_REF] Graham | On additive bases and harmonious graphs[END_REF]. It is not difficult to see that ψ cp (n) is achieved when a 1 = 0, so that the constant parity is even. Then Λ(n) can be identified with Graham and Sloane's v α (n), so that (5) also gives Λ(n) ∼ 2n 2 .

Turning this observation around shows that our (11) improves (5). This stems from the decrease in the minimum ϑ since [START_REF] Graham | On additive bases and harmonious graphs[END_REF] appeared. The present value ϑ = 21/40 (cf. 13/23 available to Graham and Sloane) improves not only (5), but also the upper bounds for the other three packing functions considered in [START_REF] Graham | On additive bases and harmonious graphs[END_REF].


Po-Shen Loh

Leonard J Schulman
email: schulman@caltech.edu

Improved Expansion of Random Cayley Graphs

Keywords: expander graphs, Cayley graphs, second eigenvalue, logarithmic generators

proved that for every ε > 0 there is a finite c(ε) such that for any sufficiently large group G, the expected value of the second largest (in absolute value) eigenvalue of the normalized adjacency matrix of the Cayley graph with respect to c(ε) log |G| random elements is less than ε. We reduce the number of elements to c(ε) log D(G) (for the same c), where D(G) is the sum of the dimensions of the irreducible representations of G. In sufficiently non-abelian families of groups (as measured by these dimensions), log D(G) is asymptotically (1/2) log |G|. As is well known, a small eigenvalue implies large graph expansion (and conversely); see Tanner (1984) and Alon and Milman (1984, 1985). For any specified eigenvalue or expansion, therefore, random Cayley graphs (of sufficiently non-abelian groups) require only half as many edges as was previously known.

Introduction

All groups considered in this paper are finite.

Definition 1 Let G be a group, and S ⊂ G be a multiset. The Cayley graph X(G, S) is the multigraph on vertex set G, with n undirected edges connecting g and tg if t appears n times in the multiset union S ⊔ S -1 , where S -1 is the multiset {s -1 : s ∈ S}. The normalized adjacency matrix A * X(G,S) is 1/(2|S|) times the adjacency matrix of X(G, S).

Definition 2 Let M be an n × n matrix with real eigenvalues x 1 , . . . , x n , where

|x 1 | ≥ • • • ≥ |x n |. Define λ(M) = |x 1 | and µ(M) = |x 2 |. Write µ(X(G, S)) for µ(A * X(G,S) ).

Definition 3 Let D(G) be the sum of the dimensions of the irreducible representations of G.

Observe that |G| 1/2 < D(G) ≤ |G|. The upper bound is met only by abelian groups but is approached also by other groups whose irreducible representations are mostly low-dimensional, such as dihedral groups. The lower bound is approached, in the sense that log D(G) → (1/2) log |G|, by a variety of families of groups possessing mostly high-dimensional irreducible representations.

Examples:

(a) The affine group A p over the prime field GF(p).

|A p | = p(p -1), while D(A p ) = 2p -2. (b) The symmetric group S n . |S n | = n!, hence log |S n | ∈ n log n -O(n), while D(S n ) ∈ e O( √ n) √ n!, hence log D(S n ) ∈ (1/2)n log n + O( √ n).
(For the upper bound on D(S n ), take the number of irreducible representations of S n times the maximum of their dimensions. The first of these is p(n), the number of partitions of n, which has the asymptotic behavior p(n) ∼ 1 4n √ 3 e π √ 2n/3 . The second was shown by [START_REF] Vershik | Asymptotics of the largest and the typical dimensions of irreducible representations of a symmetric group[END_REF] to be bounded above by e -k √ n √ n! for a positive constant k.)

Theorem 1 For any ε > 0 the following holds for every sufficiently large group G. Let S be a multiset of c(ε) log D(G) uniformly and independently sampled elements of G, for c(ε) = 4e/ε 2 . Then we have

E[µ(X(G, S))] < (1 + o(1))ε.
(Here and throughout o(1) allows for a quantity tending to 0 for large |G|.) Russell and Landau ( 2004) have independently obtained a similar result.

As a detail note that in [START_REF] Alon | Random cayley graphs and expanders[END_REF], S is generated by sampling without repetition (i.e., S is a set), while we employ sampling with repetition. The principal benefit of this is to simplify the argument, but it also leads to some sharpening: the value of c(ε) obtained in [START_REF] Alon | Random cayley graphs and expanders[END_REF] is slightly larger than given here, while substituting sampling with repetition into their argument leads to the same c(ε).

Proof

The combinatorial outline of the proof follows that of Alon and Roichman; the heart of the improvement lies in taking a certain union bound over the irreducible representations, rather than over the entire regular representation, of the group.

Decomposition into irreducible representations

F (α) = R M r=1 ∑ t∈T 1 |T | ρ r (t) ,
where ρ r : G → M r are the (unitary) irreducible representations, expressed with respect to fixed bases. Focus on an arbitrary component r of F (α):

let Ψ r = (1/|T |) ∑ t∈T ρ r (t).
Since Ψ r is an average of unitary matrices, its eigenvalues are bounded in absolute value by 1. Let ρ 1 be the one-dimensional trivial representation ρ 1 : G → C. Then for any S, Ψ 1 = 1. Therefore, µ(X(G, S)) = λ(A), where A is the following block-diagonal matrix:

A =     Ψ 2 0 . . . 0 0 Ψ 3 . . . 0 . . . . . . 0 0 . . . Ψ R     .

From eigenvalues to random walks

Fact 1 Let M be a square matrix with real eigenvalues. Then for every positive integer m,

λ(M) ≤ Tr(M 2m ) 1/2m .
Because of the symmetric construction of T , A is Hermitian. By convexity,

E[µ(X(G, S))] ≤ E[Tr(A 2m )] 1/2m .
Since A is block-diagonal, A 2m shares the same block structure, with blocks

Ψ 2m i (2 ≤ i ≤ R). Tr(A 2m ) = R ∑ r=2 Tr(Ψ 2m r ) = R ∑ r=2 ∑ t 1 ,...,t 2m ∈T χ r (t 1 • • •t 2m ) |T | 2m = R ∑ r=2 ∑ g∈G χ r (g) N g |T | 2m ,
where χ r is the character of ρ r and N g is the number of ways to produce g as a product of 2m (not necessarily distinct) elements of T .

Definition 4 Let RW denote the following random walk process.

(1) Choose a uniform random word of length 2m from the free monoid on the N letters {a 1 , a 2 , . . . , a N } (e.g., a 2 a 5 a -1 5 a -1 1 a 7 a 3 ).

(2) Reduce the word in the free group (e.g., a 2 a 5 a -1 5 a -1 1 a 7 a 3 → a 2 a -1 1 a 7 a 3 ).

(3) Uniformly and independently assign (not necessarily distinct) group elements to the letters that appear in the remaining word, and evaluate the product in G.

Let RW g be the event that the result is g.

Pr(RW g ) = N g /|T | 2m , so E[Tr(A 2m )] = ∑ g∈G Pr(RW g ) R ∑ r=2
Re χ r (g).

Mixing in the random walk

Definition 5 Let ω be a reduced word as obtained via step (2) of process RW (definition 4). Say that ω has a singleton if there is an i such that the number of occurrences of a i in ω plus the number of occurrences of a -1 i in ω is exactly one. Let Ω be the event that the reduced word has a singleton. Now:

∑ g∈G Pr(RW g ) R ∑ r=2 Re χ r (g) = ∑ g∈G Pr(Ω ∧ RW g ) R ∑ r=2 Re χ r (g) + ∑ g∈G Pr(Ω ∧ RW g ) R ∑ r=2 Re χ r (g) ≤ ∑ g∈G Pr(Ω ∧ RW g ) R ∑ r=2 Re χ r (g) + Pr(Ω)D(G).
(1)

Lemma 1 Pr(RW g |Ω) = 1/|G|.

Proof: In step (3) of RW (definition 4), assign the singleton element last; then, there will exist a unique group element that makes ω evaluate to g. ✷ Comment: This lemma replaces an upper bound of 1/|G| + O(m/G 2 ) in [START_REF] Alon | Random cayley graphs and expanders[END_REF], the additional term being the result of their requiring distinct assigments in step (3). This additional term leads in turn to an extra summand of e -b in the analogue, in their work, of the center expression in Inequality (2).

By Lemma 1 and the orthogonality of characters, the first term of Bound (1) vanishes. Combining our inequalities:

E[µ(X(G, S))] ≤ (E[Tr(A 2m )]) 1/2m ≤ Pr(Ω) 1/2m D(G) 1/2m .
To bound Pr(Ω), we follow the spirit of [START_REF] Alon | Random cayley graphs and expanders[END_REF] and define the following two events in terms of the quantity M = 2m(1log log 2m/ log 2m):

(A) After step (2) of RW (definition 4), the length of the reduced word is less than M.

(B) After step (2) of RW (definition 4), the length of the reduced word is at least M, but there are no singletons.

Fix

  a group G, and let S be a multiset of N elements of G. Let T = S ⊔ S -1 ; let α be the element in the group algebra C[G] defined by: Let the operator L be the left-action of α on C[G]. Its matrix representation with respect to the standard basis is the normalized adjacency matrix of X(G, S). The Fourier Transform F is an algebra isomorphism from C[G] to L R r=1 M r , where R is the number of irreducible representations of G, and M r = Mat d r ×d r (C). Hence the eigenvalues of L are the same as the eigenvalues of the left-action of F (α) on L M r . Explicitly,

† Supported in part by the Marshall family, a Caltech Summer Undergraduate Research Fellowship, and an NSF REU supplement. ‡ Supported in part by NSF CAREER grant 0049092 and by a grant from the Okawa Foundation. 1365-8050 c 2004

Clearly, Pr(Ω) ≤ Pr(A) + Pr(B). [START_REF] Alon | Random cayley graphs and expanders[END_REF] produced these bounds:

Substituting N = c(ε) log D(G) and 2m = (1/b) log D(G), for any constant b, we obtain an expression almost identical to one of [START_REF] Alon | Random cayley graphs and expanders[END_REF], except that |G|'s are replaced by D(G)'s:

where we use the choices c(ε) = 4e/ε 2 and b = 1/2. ✷


David R Wood
email: david.wood@upc.edu

Acyclic, Star and Oriented Colourings of Graph Subdivisions

Keywords: graph, graph colouring, star colouring, star chromatic number, acyclic colouring, acyclic chromatic number, oriented colouring, oriented chromatic number, subdivision AMS classification: 05C15

Let G be a graph with chromatic number χ(G). A vertex colouring of G is acyclic if each bichromatic subgraph is a forest. A star colouring of G is an acyclic colouring in which each bichromatic subgraph is a star forest. Let χ a (G) and χ s (G) denote the acyclic and star chromatic numbers of G. This paper investigates acyclic and star colourings of subdivisions. Let G ′ be the graph obtained from G by subdividing each edge once. We prove that acyclic (respectively, star) colourings of G ′ correspond to vertex partitions of G in which each subgraph has small arboricity (chromatic index). It follows that χ a (G ′ ), χ s (G ′ ) and χ(G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. The oriented chromatic number -→ χ (G) of an (undirected) graph G is the maximum, taken over all orientations D of G, of the minimum number of colours in a vertex colouring of D such that between any two colour classes, all edges have the same direction. We prove that -→ χ (G ′ ) = χ(G) whenever χ(G) ≥ 9.

Introduction

Let G be a (finite, simple, undirected) graph with vertex set V (G) and edge set E(G). Let δ(G) and ∆(G) denote the minimum and maximum degrees of G.

A vertex partition of G is a set {G 1 , G 2 , . . . , G k } of induced subgraphs of G such that V (G) = viewed as a function that assigns one of k colours to every vertex of G such that adjacent vertices receive distinct colours. The chromatic number χ(G) is the minimum k such that G has a vertex k-colouring.

An edge partition of G is a set {G 1 , G 2 , . . . , G k } of subgraphs of G such that E(G) = S k i=1 E(G i ) and E(G i ) ∩ E(G j ) = / 0 for all distinct i and j. An edge k-colouring of G is an edge partition {G 1 , G 2 , . . . , G k } of G in which each G i is a matching. An edge in E(G i ) is said to be coloured i, and an edge k-colouring can be viewed as a function that assigns one of k colours to every edge of G such that pairs of edges with a common endpoint receive distinct colours. The chromatic index χ ′ (G) is the minimum k such that G has an edge k-colouring.

We will mainly be concerned with vertex colourings. Henceforth a colouring will mean a vertex colouring.

A colouring of G is acyclic if every cycle receives at least three colours; that is, every bichromatic subgraph is a forest. The acyclic chromatic number χ a (G) is the minimum number of colours in an acyclic colouring of G. An acyclic colouring is a star colouring if every 4-vertex path receives at least three colours; that is, every bichromatic subgraph is a union of disjoint stars. The star chromatic number χ s (G) is the minimum number of colours in a star colouring of G. By definition every graph G satisfies χ a (G) ≤ χ s (G) .

(

) 1
It is folklore that χ s (G) ≤ χ a (G) • 2 χ a (G)-1 (see [START_REF] Fertin | On star coloring of graphs[END_REF][START_REF] Branko Gr Ünbaum | Acyclic colorings of planar graphs[END_REF]). Albertson et al. [START_REF] Albertson | Coloring with no 2-colored P 4 's[END_REF] recently improved this bound to χ s (G) ≤ χ a (G)(2χ a (G) -1). A general result by Nešetřil and Ossona de Mendez [START_REF] Ne | Colorings and homomorphisms of minor closed classes[END_REF] states that χ s (G) (and hence χ a (G)) is at most a quadratic function of the maximum chromatic number of a minor of G. Other references on acyclic and star colourings include [START_REF] Albertson | Every planar graph has an acyclic 7-coloring[END_REF][START_REF] Albertson | An acyclic analogue to Heawood's theorem[END_REF][START_REF] Noga Alon | Acyclic coloring of graphs[END_REF][START_REF] Noga Alon | On acyclic colorings of graphs on surfaces[END_REF][START_REF] Borodin | On acyclic colorings of planar graphs[END_REF][START_REF] Borodin | Acyclic list 7-coloring of planar graphs[END_REF][START_REF] Borodin | Acyclic k-strong coloring of maps on surfaces[END_REF][START_REF] Borodin | Acyclic colouring of 1-planar graphs[END_REF][START_REF] Borodin | Acyclic colourings of planar graphs with large girth[END_REF][START_REF] Šteȋn | Every 4-valent graph has an acyclic 5-coloring[END_REF][START_REF] Fertin | Minimum feedback vertex set and acyclic coloring[END_REF][START_REF] Fertin | Acyclic and k-distance coloring of the grid[END_REF][START_REF] Fertin | On star coloring of graphs[END_REF][START_REF] Iosif Fiam Čík | The acyclic chromatic class of a graph[END_REF][START_REF] Alexandr | Note to the paper of Grünbaum on acyclic colorings[END_REF][START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF][START_REF] Alexandr | Acyclic 6-coloring of planar graphs[END_REF][START_REF] John Mitchem | Every planar graph has an acyclic 8-coloring[END_REF].

A directed graph obtained from a graph G by giving each edge one of the two possible orientations is called an orientation of G. The arc set of an orientation D is denoted by A(D). A colouring of D is oriented if between every pair of colour classes, all edges have the same direction. The oriented chromatic number -→ χ (D) is the minimum number of colours in an oriented colouring of D. A tournament is an orientation of a complete graph. Observe that -→ χ (D) ≤ k if and only if there is a homomorphism φ from D to a k-vertex tournament H; that is, for every arc vw ∈ A(D), the image φ(v)φ(w) ∈ A(H).

The oriented chromatic number of an (undirected) graph G, denoted by -→ χ (G), is the maximum of -→ χ (D), taken over all orientations D of G. Oriented chromatic number is bounded by acyclic chromatic number. In particular, Raspaud and Sopena [START_REF] Sopena | Good and semi-strong colorings of oriented planar graphs[END_REF]

proved that - → χ (G) ≤ χ a (G) • 2 χ a (G)-1 .
Other reference on oriented chromatic number include [START_REF] Borodin | On deeply critical oriented graphs[END_REF][START_REF] Borodin | On universal graphs for planar oriented graphs of a given girth[END_REF][START_REF] Borodin | On the maximum average degree and the oriented chromatic number of a graph[END_REF][START_REF] Fertin | On the oriented chromatic number of grids[END_REF][START_REF] Kostochka | On the minimum number of edges giving maximum oriented chromatic number[END_REF][START_REF] Kostochka | Acyclic and oriented chromatic numbers of graphs[END_REF][START_REF] Ne | Colorings and girth of oriented planar graphs[END_REF][START_REF] Ne | T -preserving homomorphisms of oriented graphs[END_REF][START_REF] Pascal Ochem | Oriented colorings of triangle-free planar graphs[END_REF][START_REF] Sopena | Good and semi-strong colorings of oriented planar graphs[END_REF][START_REF] Sopena | The chromatic number of oriented graphs[END_REF][START_REF] Sopena | Oriented graph coloring[END_REF][START_REF] Sopena | There exist oriented planar graphs with oriented chromatic number at least sixteen[END_REF].

A subdivision of a graph G is a graph obtained from G by replacing each edge by an internally disjoint path of at least one edge. The vertices of a subdivision of G corresponding to vertices of G are said to be original vertices. The remaining vertices are called division vertices. The subdivision of G obtained by replacing each edge vw by a 3-vertex path (v, x, w) is denoted by G ′ . Clearly χ(G ′ ) ≤ 2 for every graph G.

Results

The star / acyclic / oriented chromatic numbers of G ′ are the main topics of this paper. Our results on these topics are respectively presented in Sections 3, 4, and 5. We show that star (respectively, acyclic) colourings of G ′ correspond to vertex partitions of G in which each subgraph has small chromatic index (arboricity). It follows that χ s (G ′ ), χ a (G ′ ) and χ(G) are tied, in the sense that each is bounded by a function of the other. Moreover the binding functions that we establish are all tight. We start in Section 2 with a general discussion of 'partitionable' parameters that may be of independent interest. In Section 5 we prove that -→ χ (G ′ ) is strongly tied to χ(G). In particular, -→ χ (G ′ ) = χ(G) whenever χ(G) ≥ 9. Finally in Section 6, we study the acyclic and star chromatic numbers of subdivisions in which each edge is replaced by a path of at least four vertices. We prove that such subdivisions have bounded star / acyclic / oriented chromatic numbers. A theme of this paper is that questions about graph colourings and partitions can be expressed in terms of colourings of subdivisions. Another example is that the total chromatic number of G equals the chromatic number of the square of G ′ .

Partitionable Parameters

The following result by Lovász [START_REF] Ász | On decomposition of graphs[END_REF], which will be used in Section 3, says that the maximum degree is a 'partitionable' parameter; see [START_REF] Bernardi | On a theorem about vertex colorings of graphs[END_REF][START_REF] Manvel | Optimal vertex partitions[END_REF][START_REF] Borowiecki | A survey of hereditary properties of graphs[END_REF][START_REF] Va | Remark on a paper of Lovász[END_REF][START_REF] Ászl | On coloring problems[END_REF][START_REF] Lawrence | Covering the vertex set of a graph with subgraphs of smaller degree[END_REF][START_REF] Mozhan | Density and n-clique chromatic number[END_REF] for related work.

Lemma 1 ([38]). Let G be a graph. Let d 1 , d 2 , . . . , d k be non-negative integers such that

∑ k i=1 d i = ∆(G) - k + 1. Then G has a vertex partition {G 1 , G 2 , . . . , G k } in which ∆(G i ) ≤ d i for all i.
A graph is chordal if it contains no induced cycle on at least four vertices. The treewidth tw(G) is the minimum k such that the graph G is a subgraph of a chordal graph with no (k + 2)-clique. The following result by Ding et al. [START_REF] Guoli Ding | Partitioning graphs of bounded tree-width[END_REF] says that treewidth is partitionable.

Lemma 2 ([23]). Let d 1 , d 2 , . . . , d k be non-negative ‡ integers such that ∑ k i=1 d i = d -k + 1. Then every graph G with treewidth tw(G) ≤ d has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i has treewidth tw(G i ) ≤ d i .
The degeneracy of G is defined to be

d(G) = max H⊆G δ(H) .
A graph with degeneracy at most d is d-degenerate. The following result due to Mihók [START_REF] Peter Mih Ók | Minimal reducible bounds for the class of k-degenerate graphs[END_REF] says that degeneracy is partitionable. We include the proof (which was discovered independently) for completeness. [START_REF] Lick | k-degenerate graphs[END_REF][START_REF] John Mitchem | An extension of Brooks' theorem to n-degenerate graphs[END_REF]

G \ v is also d-degenerate. By induction, G \ v has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i is d i -degenerate. There is some i such that G i contains at most d i neighbours of v, as otherwise v has degree at least ∑ k i=1 (d i + 1) = d + 1. Let H be the subgraph of G induced by V (G i ) ∪ {v}. It follows that H is also d i -degenerate (see
for example). Thus {G 1 , . . . , G i-1 , H, G i+1 , . . . , G k } is the desired vertex partition of G.
It is easily seen that Theorem 1 is best possible for the complete graph K n with n ≡ 0 (mod k(k + 1)), and

d i = d j for all 1 ≤ i < j ≤ k.
For planar graphs, which are 5-degenerate, stronger results than Theorem 1 are possible. The 4colour theorem [START_REF] Robertson | The fourcolour theorem[END_REF] states that every planar graph has a vertex partition into four 0-degenerate subgraphs. Strengthening the 5-colour theorem, Thomassen [START_REF] Thomassen | Decomposing a planar graph into degenerate graphs[END_REF] proved that every planar graph has a vertex partition into a 2-degenerate subgraph and a 1-degenerate subgraph (a forest), and Thomassen [START_REF] Thomassen | Decomposing a planar graph into an independent set and a 3-degenerate graph[END_REF] proved that every planar graph has a vertex partition into a 3-degenerate subgraph and a 0-degenerate subgraph.

The arboricity a(G) is the minimum k such that the graph G has an edge partition {G 1 , G 2 , . . . , G k } in which each G i is a forest. Nash-Williams [START_REF] St | Decomposition of finite graphs into forests[END_REF] proved that

a(G) = max H⊆G |E(H)| |V (H)| -1 . (2)
It is well known that (see [START_REF] Nishizeki | Edge-coloring and f -coloring for various classes of graphs[END_REF] for example)

a(G) ≤ d(G) ≤ 2 a(G) -1 , (3)
and

χ(G) ≤ d(G) + 1 ≤ 2 a(G) . (4)
To what extent arboricity is a partitionable parameter will be important in Section 4. Theorem 1 and (3) imply:

Corollary 1. Let G be a graph with degeneracy d(G) ≤ d (which is implied if G has arboricity a(G) ≤ 1 2 (d + 1)). Let d 1 , d 2 , . . . , d k be non-negative integers such that ∑ k i=1 d i = d -k + 1. Then G has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i has arboricity a(G i ) ≤ d i .

Corollary 2. Let G be a graph with arboricity

a(G) ≤ d. Let d 1 , d 2 , . . . , d k be non-negative integers such that ∑ k i=1 d i = 2d -k. Then G has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i has arboricity a(G i ) ≤ d i .

Star Colourings of G ′

In this section we study the star chromatic number of G ′ . First we give a simple upper bound on χ s (G ′ ) in terms of χ(G). Lemma 3. For every graph G, χ s (G ′ ) ≤ max{χ(G), 3}.

Proof. Consider a colouring of G with χ(G) colours. Define a colouring of G ′ in which each original vertex inherits its colour from G. If χ(G) ≤ 2 then let all the division vertices receive one new colour. Otherwise (if χ(G) ≥ 3), for each division vertex, choose one of the χ(G) colours different from the two colours assigned to its two neighbours. A 4-vertex path in G ′ contains a trichromatic path (v, x, w), where x is the division vertex of the edge vw. Thus G ′ has a star colouring with max{χ(G), 3} colours.

In Lemma 3, the original vertices of G ′ inherit their colour from a colouring of G. At the other extreme, the original vertices of G ′ are monochromatic.

Lemma 4. For every graph G, the minimum number of colours in a star colouring of G ′ in which the original vertices are monochromatic is χ

′ (G) + 1.
Proof. Given an edge colouring of G, transfer the colour from each edge to the corresponding division vertex, and colour all of the original vertices with a new colour. Let P = (v, x, w, y) be a 4-vertex path of G ′ . Without loss of generality, x is the division vertex of the edge vw, and y is the division vertex of some edge wu. In the edge colouring, vw and wu receive distinct colours. Hence x and y receive distinct colours, and P is not bichromatic. Thus G ′ has a star colouring with χ ′ (G) + 1 colours in which the original vertices are monochromatic.

Consider a star colouring of G ′ with k colours in which the original vertices are monochromatic. No division vertex can receive this colour, otherwise it is not a colouring. For all pairs of edges of G with an endpoint in common, the corresponding division vertices receive distinct colours, as otherwise there is a bichromatic 5-vertex path in G ′ . Transferring the colour from each division vertex of G ′ to the corresponding edge of G, we obtain an edge (k -1)-colouring of G.

Theorem 2. For every graph G, the star chromatic number of G ′ satisfies:

χ(G) ≤ χ s (G ′ ) ≤ max{χ(G), 3} . Proof. The upper bound is Lemma 3. Let φ be a star k-colouring of G ′ , where k = χ s (G ′ ). Let H be the spanning subgraph of G with edge set E(H) = {vw ∈ E(G) : φ(v) = φ(w)}. Then every connected component of H is monochromatic under φ. By Lemma 4, χ ′ (H) ≤ k -1. Hence ∆(H) ≤ k -1, and thus χ(H) ≤ k by Brooks' Theorem [20]. Let ϕ be a vertex k-colouring of H. Now colour each vertex v ∈ V (G) by the pair (φ(v), ϕ(v)). Consider an edge vw ∈ E(G). If vw ∈ E(H) then ϕ(v) = ϕ(w). If vw ∈ E(H) then φ(v) = φ(w). Thus we have a k 2 -colouring of G, and χ(G) ≤ χ s (G) 2 .
We now take an approach that is somewhere between the extremes of Lemmata 3 and 4.

Lemma 5.

Let G be a graph, and let k ≥ 1 and d ≥ 0 be integers. Suppose that G has a vertex partition

{G 1 , G 2 , . . . , G k } in which χ ′ (G i ) ≤ d for all 1 ≤ i ≤ k. Then χ s (G ′ ) ≤ max{k + 1, d + 2}. Proof. Let m = max{k, d + 1} and [m] = {0, 1, . . . , m -1}. For each vertex v ∈ V (G i ), let φ(v) = i -1. Thus φ(v) ∈ [m]. For 1 ≤ i ≤ k, let λ i be an edge d-colouring of G i , where 1 ≤ λ i (vw) ≤ d. Consider an edge vw of G whose division vertex in G ′ is x. First suppose that φ(v) = φ(w) = i. Let φ(x) = (i + λ i (vw)) mod m. Since i ∈ [m] and m > d ≥ λ i (vw) ≥ 1, φ(x) ∈ [m] \ {i}. If φ(v) = φ(w), then let φ(x) = m.
In both cases, x is coloured differently from both of its neighbours. Hence φ is a colouring of G ′ . Suppose that φ is not a star colouring. That is, there is a path P = (v, x, w, y) in G ′ , and φ(v) = φ(w) = φ(x) = φ(y). Without loss of generality, x is the division vertex of the edge vw, and y is the division vertex of some edge wu. First suppose that φ(v) = φ(w) = φ(u). Then vw and wu are in some G i . Hence the edge colours of vw and wu are distinct, and

φ(x) = φ(y), a contradiction. If φ(v) = φ(w) = φ(u) then φ(x) ≤ m -1 and φ(y) = m, a contradiction. Therefore φ is a star colouring of G ′ with m + 1 = max{k + 1, d + 2} colours.
Converse to Lemma 5, we have the following.

Lemma 6. For every graph G, if χ s (G ′ ) ≤ k then G has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i has chromatic index χ ′ (G i ) ≤ k -1. Proof. Let φ be a star k-colouring of G ′ . Let {G 1 , G 2 , . . . , G k } be the vertex partition of G, where V (G i ) = {v ∈ V (G) : φ(v) = i}. By Lemma 4, χ ′ (G i ) ≤ k -1 for all i. Theorem 3. For every graph G, χ s (G ′ ) ≤ ∆(G) + 3. Proof. Let ∆ = ∆(G) and k = ⌈ √ ∆⌉. Let d 1 , d 2 , . . . , d k ∈ {⌊(∆ -k + 1)/k⌋, ⌈(∆ -k + 1)/k⌉} such that ∑ k i=1 d i = ∆ -k + 1. By Lemma 1, G has a vertex partition {G 1 , G 2 , . . . , G k } in which ∆(G i ) ≤ d i ≤ ⌈(∆ -k + 1)/k⌉ ≤ ∆/k ≤ √ ∆ for all i. By Vizing's Theorem [55], χ ′ (G i ) ≤ √ ∆ + 1. By Lemma 5, χ s (G ′ ) ≤ max{⌈ √ ∆⌉ + 1, √ ∆ + 3} ≤ √ ∆ + 3.
The following example shows that, up to the additive constant, the lower bound in Theorem 2 and the upper bound in Theorem 3 are tight.

Example 1. For all n

≥ 1, √ n ≤ χ s (K ′ n ) ≤ √ n -1 + 3.
We now prove that the upper bound in Theorem 2 is tight. Let K(n 1 , n 2 , . . . , n k ) denote the complete k-partite graph with n i vertices in the i-th colour class.

Example 2. For all k ≥ 3 and n

≥ k -1, the complete k-partite graph G = K(n, n, . . . , n) satisfies χ s (G ′ ) = k (= χ(G)). Proof. That χ s (G ′ ) ≤ k follows from Lemma 3. Suppose on the contrary, that χ s (G ′ ) ≤ k -1. By Lemma 6, G has a vertex partition {G 1 , G 2 , . . . , G k-1 } in which χ ′ (G i ) ≤ k -2 for all i, which implies that ∆(G i ) ≤ k -2. For some 1 ≤ i ≤ k -1, |V (G i )| ≥ |V (G)|/(k -1) = kn/(k -1). For some 1 ≤ j ≤ k, the number of vertices in V (G i ) that are in the j-th colour class of G is at most |V (G i )|/k. Let v be such a ver- tex. Vertices in distinct colour classes of G are adjacent. Thus v is adjacent to at least |V (G i )| -|V (G i )|/k vertices in G i . That is, ∆(G i ) ≥ (k -1)|V (G i )|/k ≥ n.
Thus we obtain the desired contradiction for n ≥ k -1.

Acyclic Colourings of G ′

In this section we study the acyclic chromatic number of G ′ . The results are analogous to those for the star chromatic number in Section 3, with arboricity playing the same role as chromatic index. We start with an analogue of Lemma 4.

Lemma 7.

For every graph G, the minimum number of colours in an acyclic colouring of G ′ in which the original vertices are monochromatic is a(G) + 1.

Proof. Suppose we have an acyclic (k + 1)-colouring of G ′ in which the original vertices are monochromatic. Then no division vertex receives the same colour as the original vertices. The edge partition of G defined with respect to the colour of the corresponding division vertex consists of k acyclic subgraphs, and a(G) ≤ k. Conversely, given an edge partition {G 1 , G 2 , . . . , G k } of G into forests, let i be the colour of each division vertex of an edge in G i , and colour each original vertex 0. We obtain an acyclic (k + 1)-colouring of G ′ in which the original vertices are monochromatic.

Lemma 8. Let d ≥ 0 and k ≥ 1 be integers. If a graph G has a vertex partition {G

1 , G 2 , . . . , G k } in which each G i has arboricity a(G i ) ≤ d, then G ′ has acyclic chromatic number χ a (G ′ ) ≤ max{k, d + 1, 3}. Proof. For each vertex v ∈ V (G i ), let φ(v) = i -1. Let m = max{k, d + 1, 3} and [m] = {0, 1, . . . , m -1}. Thus φ(v) ∈ [m]. For 1 ≤ i ≤ k, let {G i,1 , G i,2 , . . . , G i,d } be an edge partition of G i into forests. Consider an edge vw of G whose division vertex in G ′ is x. First suppose that φ(v) = φ(w) = i. Let φ(x) = (i + j) mod m, where vw ∈ E(G i, j ). Since i ∈ [m] and m > d ≥ j ≥ 1, φ(x) ∈ [m] \ {i}. Now suppose that φ(v) = φ(w). Choose φ(x) ∈ [m] \ {φ(v), φ(w)}.
Since m ≥ 3 there is such a colour. In both cases, x is coloured differently from both of its neighbours. Hence φ is a colouring of G ′ .

Suppose on the contrary that under φ, there is a bichromatic cycle C in G ′ . Then for some t, C = (v 0 , x 0 , v 1 , x 1 , . . . , v t-1 , x t-1 ), where each v α is an original vertex, each x α is the division vertex of v α v α+1 (modulo t), and φ(v α ) = φ(v β ) and φ(x α ) = φ(x β ) for all α and β. Thus by the definition of φ, for some 1 ≤ i ≤ k, every vertex v α ∈ V (G i ), which implies that for some 1 ≤ j ≤ d, every edge v α v α+1 ∈ E i j . Hence G i, j contains a cycle, a contradiction. Thus φ is an acyclic m-colouring of G ′ . Theorem 4. Let G be a graph and k ≥ 2 be an integer. Then

χ a (G ′ ) ≤ k if and only if G has a vertex partition {G 1 , G 2 , . . . , G k } in which each G i has arboricity a(G i ) ≤ k -1. Proof. (⇐) This is Lemma 8 with d = k -1.
(⇒) Consider the vertex partition of G defined by an acyclic k-colouring of G ′ (restricted to G). By Lemma 7, each subgraph has at most k -1.

Theorem 5. For every graph G with degeneracy

d(G) ≤ d (which is implied if G has arboricity a(G) ≤ 1 2 (d + 1)), χ a (G ′ ) ≤ max{ √ d + 1, 3}. Proof. Let k = ⌈ √ d⌉. Let d 1 , d 2 , . . . , d k ∈ {⌊(d -k + 1)/k⌋, ⌈(d -k + 1)/k⌉} such that ∑ k i=1 d i = d -k + 1. By Corollary 1, G has a vertex partition {G 1 , G 2 , . . . , G k } in which a(G i ) ≤ d i ≤ ⌈(d -k + 1)/k⌉ ≤ d/k ≤ √ d for all i. By Lemma 8, χ a (G ′ ) ≤ max{⌈ √ d⌉, √ d + 1, 3} = max{ √ d + 1, 3}. Theorem 6. For every graph G, if χ a (G ′ ) ≤ k then χ(G) ≤ 2k(k -1). Proof. Let φ be an acyclic k-colouring of G ′ . Let H be the spanning subgraph of G with edge set E(H) = {vw ∈ E(G) : φ(v) = φ(w)}.
Then every connected component of H is monochromatic under φ. By Lemma 7, H has arboricity at most k -1. By ( 4), H has a vertex 2(k -1)-colouring ϕ. Now colour each vertex v ∈ V (G) by the pair (φ(v), ϕ(v)). Consider an edge vw ∈ E(G).

If vw ∈ E(H) then ϕ(v) = ϕ(w). If vw ∈ E(H) then φ(v) = φ(w).
Thus we have a 2k(k -1)-colouring of G.

Lemma 3 and Theorem 6 and (1) imply that χ a (G ′ ) is tied to χ(G).

Corollary 3.

For every graph G, the acyclic chromatic number of G ′ satisfies:

1 2 χ(G) < χ a (G ′ ) ≤ max{χ(G), 3} .
The following example shows that the lower bound in Corollary 3 is tight up to an additive constant.

Example 3. For all n, n/2 < χ a (K ′ n ) < n/2 + 5 2
Proof. The lower bound follows from Corollary 3. Now we prove the upper bound. Observe that a(

K n ) = ⌈n/2⌉ by (2). Let k = ⌈ n/2⌉. Let {G 1 , G 2 , . . . , G k } be a vertex partition of K n , in which |V (G i )| ∈
{⌊n/k⌋, ⌈n/k⌉} for all i. By the above observation,

a(G i ) ≤ 1 2 ⌈n/k⌉ ≤ 1 2 ⌈n/ n/2⌉ = 1 2 ⌈ √ 2n⌉ < 1 2 ( √ 2n + 1) = n/2 + 1 2 .
By Lemma 8, K ′ n has acyclic chromatic number

χ a (K ′ n ) ≤ max ⌈ n/2⌉, ⌈ n/2 + 1 2 ⌉ + 1, 3 < n/2 + 5 2 .
We now prove that the above upper bound in Corollary 3 is tight. Proof. That χ a (G ′ ) ≤ k follows from Corollary 3. Suppose on the contrary, that

χ a (G ′ ) ≤ k -1. By Theorem 4, G has a vertex partition {G 1 , G 2 , . . . , G k-1 } in which each G i has arboricity a(G i ) ≤ k -2.
For some 1

≤ i ≤ k -1, |V (G i )| ≥ |V (G)|/(k -1) = kn/(k -
a(H) ≥ (k -1)(m -(k -1)) m -1 = k -1 - (k -1)(k -2) m -1 .
Applying this observation with H = G i and m ≥ kn/(k -1), we have

a(G i ) ≥ k -1 - (k -1)(k -2) kn/(k -1) -1 . Since a(G i ) ≤ k -2, it follows that we obtain a contradiction for n > n(k) = ((k -1) 2 (k -2) + (k - 1
))/k.

Oriented Colourings of G ′

We now relate the oriented chromatic number of G ′ to the chromatic number of G.

Theorem 7. For every graph G, the oriented chromatic number of G ′ satisfies

χ(G) ≤ - → χ (G ′ ) ≤      7 if χ(G) ≤ 7 9 if χ(G) = 8 χ(G) if χ(G) ≥ 9 .
Proof. First we prove the lower bound (which is well known). Let D ′ be an orientation of G ′ in which each division vertex has one incoming arc and one outgoing arc. Consider an edge vw ∈ E(G) whose division vertex in G ′ is x. In any oriented colouring of D ′ , v and w receive distinct colours, as otherwise the arcs vx and xw (or xv and wx) are in opposite directions between the same pair of colour classes. Thus an oriented colouring of D ′ contains a colouring of G.

Hence - → χ (D ′ ) ≥ χ(G), which implies that G ′ has oriented chromatic number - → χ (G ′ ) ≥ χ(G).
Now for the upper bound. A tournament H is k-existentially closed if for every k-element set of vertices S ⊆ V (H) and for every (possibly empty) T ⊆ S, there is a vertex z ∈ V (H)\(S∪T ) such that vz ∈ A(H) for every vertex v ∈ S \ T , and zw ∈ A(H) for every vertex w ∈ T . Almost every sufficiently large tournament Case 1. k ≡ 0 (mod 3) and k = 6: Let φ(x i ) = i mod 3 for all i, 0 ≤ i ≤ k -6. Let φ(x k-5 ) = 2, φ(x k-4 ) = 1, and φ(x k-3 ) = 0. Hence P is coloured (2, 012, 012, . . . , 012, 0, 210, 2). Case 2. k ≡ 1 (mod 3): Let φ(x i ) = i mod 3 for all i, 0 ≤ i ≤ k -5. Let φ(x k-4 ) = 1 and φ(x k-3 ) = 0. Hence P is coloured (2, 012, 012, . . . , 012, 10, 2). Case 3. k ≡ 2 (mod 3): Let φ(x i ) = i mod 3 for all i, 0 ≤ i ≤ k -4. Let φ(x k-3 ) = 0. Hence P is coloured (2, 012, 012, . . . , 012, 01, 0, 2).

If Q is a 4-vertex path in X with at least two original vertices then Q = (v, x 0 , x 1 , w), where Q replaced an edge vw of G, and by Case 2 with k = 4, Q is coloured (2, 1, 0, 2), and is thus not bichromatic.

If the edge vw of G is replaced by the path (v, x 0 , x 1 , . . . , x k-3 , w), then the subpaths (v, x 0 , x 1 ) and (w, x k-3 , x k-2 ) are trichromatic. (This is not the case if k = 6.) Thus a 4-vertex path containing exactly one original vertex is not bichromatic.

The case-analysis above shows that there is no bichromatic 4-vertex path with no original vertex. Thus there is no bichromatic 4-vertex path in X. Therefore χ s (X) ≤ 3.

Lemma 11. Let X be a subdivision of a graph G in which every edge of G is replaced in X by a path with at least four vertices; that is, every edge is subdivided at least twice. Then χ s (X) ≤ 4.

Proof. In the proof of Lemma 10, the only obstruction to X having a star colouring with three colours is an edge vw of G that is replaced in X by a 6-vertex path P = (v, x 0 , x 1 , x 2 , x 3 , w). In this case we introduce a fourth colour, and P can be coloured (2, 0, 1, 3, 0, 2). Let G ′′ be the subdivision of a graph G with every edge vw of G replaced by a 4-vertex path with endpoints v and w; that is, every edge is subdivided twice.

A k-cycle in G becomes a 3k-cycle in G ′′ . Thus G is bipartite if and only if G ′′ is bipartite. If G contains an odd cycle, then χ(G ′′ ) = χ s (G ′′ ) = χ a (G ′′ ) = 3.
This provides an infinite family of graphs for which the chromatic number, star chromatic number and acyclic chromatic number coincide.

Finally we consider oriented colourings of subdivisions other than G ′ .

Lemma 12. Let X be a subdivision of a graph G in which every edge of G is replaced in X by a path with at least four vertices; that is, every edge is subdivided at least twice. Then -→ χ (X) ≤ 5.

Proof. Let H be the tournament with V (H) = {0, 1, 2, 3, 4}, where i j ∈ A(H) if and only if ( ji) mod 5 ∈ {1, 2}. Let D be an orientation of X. We will construct a homomorphism φ from D to H. First define φ(v) = 0 for every original vertex v of X. Consider the path (v = d 0 , d 1 , d 2 , . . . , d t-1 , w = d t ) in X corresponding to an edge vw ∈ E(G). Then t ≥ 3. For 1 ≤ i ≤ t, define x i = 1 if d i-1 d i ∈ A(D), and define x i = -1 if d i d i-1 ∈ A(D). By Lemma 13 below, there exist y 1 , y 2 , . . . , y t such that y i ∈ {1, 2} and ∑ t i=1 x i y i ≡ 0 (mod 5). For 1 ≤ i ≤ t -1, set φ(d i ) = (∑ i j=1 x j y j ) mod 5. Consider 1 ≤ i ≤ t. We have φ(d i ) -φ(d i-1 ) ∈ {1, 2} whenever x i = 1; that is, when d i-1 d i ∈ A(D). Similarly φ(d i ) -φ(d i-1 ) ∈ {-1, -2} whenever x i = -1; that is, when d i d i-1 ∈ A(D). By the definition of H, φ(d i-1 )φ(d i ) ∈ A(H) for all 1 ≤ i ≤ t. Hence φ is a homomorphism from D to H, and -→ χ (X) ≤ 5.

Lemma 13. For all integers t ≥ 3 and x 1 , x 2 , . . . , x t ∈ {1, -1}, there exist y 1 , y 2 , . . . , y t such that y i ∈ {1, 2} and ∑ t i=1 x i y i ≡ 0 (mod 5).

Proof. Initially set every y i = 1. If ∑ t i=1 x i y i ≡ 0 (mod 5), then we are done. Now suppose that ∑ t i=1 x i y i ≡ 1 (mod 5). If there exists x i = -1, then set y i = 2, and we are done. Otherwise every x i = 1. Thus t ≡ 1 (mod 5) and t ≥ 6. Set y 1 = y 2 = y 3 = y 4 = 2, and we are done. Now suppose that ∑ t i=1 x i y i ≡ 2 (mod 5). If there exists x i = x j = -1 for some i = j, then set y i = y j = 2, and we are done. If there exists i such that x i = -1 and x j = 1 for all j = i, then t -2 ≡ 2 (mod 5) and t ≥ 4; set y j = y k = y ℓ = 2 for some distinct j, k, ℓ = i, and we are done. Otherwise every x i = 1. Thus t ≡ 2 (mod 5) and t ≥ 7. Set y 1 = y 2 = y 3 = 2, and we are done.

The cases when ∑ t i=1 x i y i ≡ 3 (mod 5) and ∑ t i=1 x i y i ≡ 4 (mod 5) are symmetric.

Example 4 .

 4 For all k ≥ 3 and n > n(k), the complete k-partite graph G = K(n, n, . . . , n) satisfies χ a (G ′ ) = k (= χ(G)).

  [START_REF] Albertson | Every planar graph has an acyclic 7-coloring[END_REF]. It is easily seen that any complete k-partite graph H on m vertices has arboricity at least the arboricity of the complete k-partite graph K(1, 1, . . . , 1, m -(k -1)). This graph has (k -1)(m -(k -1)) edges. By (2),

‡ Ding et al.[START_REF] Guoli Ding | Partitioning graphs of bounded tree-width[END_REF] state Lemma 2 for positive integers d 1 , d 2 , . . . , d k . It is easily seen that the proof is still valid if some d i = 0. A graph has treewidth 0 if and only if it has no edges.

Acknowledgements

Thanks to Ferran Hurtado and Prosenjit Bose for graciously hosting the author. Thanks to Pascal Ochem for a number of instructive comments. Thanks to an anonymous referee for pointing out an error in the original submission.

† Supported by grant MEC SB2003-0270. Partially completed at the School of Computer Science, and the

is n-existentially closed (see [START_REF] Louis Caccetta | On tournaments with a prescribed property[END_REF][START_REF] Cameron | On an adjacency property of almost all tournaments[END_REF][START_REF] Paul Erd Ős | On a problem in graph theory[END_REF]). Note that a tournament H is 2-existentially closed if and only if for every pair of vertices v, w ∈ V (H), there exists four other vertices a, b, c, d ∈ V (H) such that va, wa, bv, bw, vc, cw, dv, wd ∈ A(H) .

(

Bonato and Cameron [START_REF] Cameron | On an adjacency property of almost all tournaments[END_REF] proved that there is a

Clearly φ is a homomorphism from D ′ to H. Thus -→ χ (G ′ ) ≤ n.

Large Subdivisions

In this section we consider colourings of subdivisions other than G ′ . First we consider acyclic colourings.

Lemma 9. Let X be a subdivision of a graph G in which every edge of G is replaced in X by a path with at least four vertices; that is, every edge is subdivided at least twice. Then χ a (X) ≤ 3.

Proof. Let φ(v) = 2 for every original vertex v of X. Let D be an arbitrary orientation of G. Consider an arc vw ∈ A(D) that is replaced by a path (v, x 0 , x 1 , . . . , x k , w) in X (for some k ≥ 1). Let φ(x i ) = i mod 2. Every cycle of X contains a 3-vertex path (v, x 0 , x 1 ), which is coloured (2, 0, 1). Thus φ is an acyclic 3-colouring of X.

Now we consider star colourings of subdivisions other than G ′ .

Lemma 10. Let X be a subdivision of a graph G such that for every edge vw of G, for some k ≥ 4 with k = 6, vw is replaced by a k-vertex path in X. Then χ s (X) ≤ 3.

Proof. Colour each original vertex φ(v) = 2. Consider an edge vw of G that is replaced by the k-vertex path P = (v, x 0 , x 1 , . . . , x k-3 , w) in X.