Edouard Breniaux

Edelmy J Marin-Bernardez

Emilie Gallet

Pascal Dufour

Christophe Tenailleau
email: tenailleau@chimie.ups-tlse.fr

Synthesis and characterization of Cs 2 Pb 1 _ x Bi x C1 2 h (0 ::::; x < 0.15) derivative perovskite

Keywords:

HIGHLIGH TS • First Bi doping of 2D RP-type Cs2PbCl212 phase obtained by mechanical synthesis atRT. • XRD data analysis and Rietveld re finements show a unit cell decrease upon Bi doping. • A strong red-shift is observed with increasing x in Cs 2 Pb1-x BixCbI2 (0 :S x � 0.15). • Microstrains are generated in the Bi doped Cs2PbCl212 structures.

Introduction

GRA PHICAL ABSTRA CT ABSTRA CT

Mechanosynthesis was used to obtain pure crystalline powders of a 2D Ruddlesden-Popper type Cs2(Pb1.x Bi x) Cbl2 phase, with O � x :$ 0.15. These newly discovered compounds present interesting physical properties that may make them suitable for electronic devices, including LEDs and photovoltaics. Detailed structural analysis based on X-ray diffraction (XRD) data shows that lead substitution by bismuth reduces the unit cell parameters. A significant color change of the material has been observed with a clear red-shift related to the Bi doping content. The introduction of bismuth into the structure also induces strains as evidenced by XRD peak enlargemen'OE but the material can be pure up to x = 15 mol.%. A first ageing study shows that these strains seem to be released with time and that Cs2PbCli lz and 5 mol.% Bi-doped Cs2PbCli lz materials remain pure after a month in air.

The world energy consumption is consistently increasing. Even tbough fossil resources represent most of tbe energy sources today, tbeir prominent limitations make renewable systems essential for tbe future of humanity. Photovoltaic technology is one of tbem, even tbough it is currently limited by the efficiency, durability and cost of solar panels. In order to make solar energy more competitive and spread ail over the world, optimizations need to be made in photovoltaics. This recent tecbnology based on halicte perovskites has revived tbe interest for photovoltaics, with 3.8% efficiency obtained in 2009 and over 25.2% PCE reached 10 years la ter. It represents one of tbe fast est increase in efficiency seen for a photovoltaic technology [START_REF] Kojima | Organometal halide perovskites as visible-light sensitizers for photovoltaic cells[END_REF]2]. Due to tbese fantastic results, perovskites are becoming an important ambassador for solar energy. It is currently on tbe way to industrialization, as many companies are collaborating with laboratories to develop the manufacturing of stable devices. Moreover, it.s properties make perov skites a good candidate for a whole variety of optoelectronic devices such as photodetectors, LED, Quantum-dots for electroluminescence, lasers, or memory devices . . . The remaining limitation is its high sensitivity to ambient conditions, particularly to oxygen and moisture. Encapsulated systems have to be developed in order to operate solar panel for decades, in a similar way to silicon based solar cells [START_REF] Wong-Stringer | High-perfonnance multilayer encapsulation for perovskite photovoltaics[END_REF].

To improve the halide perovskite stability, the decrease of its dimensionality has been proven efficient. lnserting spacers in the perovskite structure in order to disconnect blocks of octahedra in some directions (but not ail) is one solution. Moisturizing effects seem then to be slowed down and the system stability improved. Usually, those spacers are organic molecules such as Butylammonium (BA) [START_REF] Liao | Dimension engineering on cesium lead iodide for efficient and stable perovskite solar cells[END_REF], Phe nylethylammonium (PEA) [START_REF] Lee | 2D perovskite stabilized phase-pure fonnainidinium perovskite solar cells[END_REF] or Hexylammonium (HA) [ To further simplify the synthetic procedure and in order to perform bismuth doping, we used the mechanosynthetis approach. This simple technique has also recently been used for the preparation of 3D inor ganic perovskites and 2D hybrid perovskites [START_REF] Rosales | Synthesis and mixing of complex halide perovskites by solvent-free solid-state method.s[END_REF][START_REF] Pal | All-Solid-state mechanochemical synthesis and post-synthetic transformation of inorganic perovskite-type halides[END_REF][START_REF] Sadhukhan | Solvent-free solid-state synthesis of high yield mixed halide perovskites for easily nmable composition and band gap[END_REF].

This paper describes the first preparation of Bi-doped Cs2PbC1 2 I 2 by mechanical synthesis al room temperature without any solvent, the ef fects of the doping agent over the structure stability and their optical properties.

Materials and methods

Lead chloride powders (PbC12, 98%), caesium iodide powders (Cs!, 99. 9%) and bismuth chloride powders (BiC1 3 98%) were purchased from Sigma-Aldrich.

Ball milling was conducted with a RETSCH PM 100 miller in an alumina bowl with 9 x 10 mm diameter alumina balls at 100 rpm up to a couple ofhours. X-Ray Diffraction (XRD) measurements were conducted on a BRUKER AXS D4 Endeavor apparatus with a Copper X-ray source (wavelengths of 0.1541 nm and 0.1543 nm for K alpha 1 and 2, respectively). X-ray Fluorescence (XRF) measurements were operated on a BRUKER S2 Ranger apparatus equipped with a Palladium X-Ray source. UV-Visible absorbance was characterized with an AGILENT Uv-Vis-Nir CARY 5000 system on powders, by reflectance measurement using an integration sphere. Scanning Electron Microscopy (SEM) images were obtained on FEG JEOL JSM 7800F equipped with a Schottky type field emission. From the XRD data analysis, we also noticed that ail peaks were broader after Bi doping, especially compared to the undoped sample. This peak enlargement proportional to the Bi content increase is hard to explain although it was already reported in a recent work [START_REF] Nayak | Impact of Bi 3 + heterovalent doping in organic-inorganic metal halide perovskite crystals[END_REF]. While it might be related to a certain degree of amorphization upon ball milling, it is actually probably due to structural deformations and in particular to the octaliedral environment modifications and tilting in the perovskite derivative structure. Distorted polyhedra due to Bi-doping that exhibit a cr non-bonding pair of electrons or site disorder are common in mdde perovskites. !.one pairs can create a lattice anharmonicity. Lead halide perovskites are actually among the most anharmonic materials. But Pb 2+ presents similar features than Bi 3+ , so the large electrostatic re pulsions created by the anion environment over the sigma orbitais should not change much from one to another if the substitution occurs at the octaliedral site. Unfortunately, the free pair position is difficult to determine by X-ray diffraction due to its low density compared to the heavy atoms. FWHM broadening can be related to a change of crystallite size and/or microstrains. While crystallite sizes could not be determined after Rietveld refinement, SEM images tend to show a decrease in par ticle sizes upon Bi-doping and after ball milling (Fig. 3). This tendency was confirmed by particles size measurements performed on at Jeast one hundred of particles for each image analyzed, as shown in Fig. 4

Results and discussion

Synthesis and structural characterization

Halogenated precursors in stoichiometric proportions

. Hu et al. also observed an effect of size diminution in Bi-doped CsPbls for nanocrystalline thin films used for solar cells [9]. The Rietveld refinement method can also give information about the microstructural characteristics of materials, based on Scherrer' s formula and Williamson-Hall method. In this case, a Voigt function has to be applied by first generating a profile function that will be used as a reference for future XRD sample data refinements. The microstructural values are given for each individual reflection in order to take into ac count possible anisotropie effect. An apparent size close to infinity was

given after Rietveld refinement meaning that no crystal size broadening could be determined.

0%

� .J , 1 5% f -,- � \\ 1/ ' 100nm 100nm - - 10% f 15%� ;'f � - ")-� �- �} -- "' -.;
1,0�::t 100 , 'll"" y.

- ---,-----�-�-�-------350 Biato. % The microstrains and crystal planes distortions consistently increased upon doping in their organic-inorganic 3D perovskite samples. In our work, the milling time was exactly the same for the undoped and 5% Bi-doped sample so it is hard to attribute the peak broadening in the XRD data to this effect alone. Still, microstrains increase with Bi doping while particles size decrease. This common inversed feature can be directly related to the heterovalent doping effect with the introduction of a smaller cation with a higher oxidation state (and possibly cation vacancies) into the 2D perovskite-derivative structure with a general cell decrease and a shortening of the (semi)metal-anion distances, especially in the inner planes of the octahedral layers, inducing particle size decrease and microstrains increase.

XRF measurements show that Bi is in the appropriate proportion for each sample (Fig. 5). These values were confirmed by EDS analysis (see supplementary information S2). While lead concentration decreases, the bismuth amount increases with the same rate. This result confirms that we successfully substituted lead by bismuth and corroborates the XRD data obtained for our synthesized samples.

Opw-electronic properties

Meta! doping of materials has been widely developed in many fields in order to improve light absorption and thus efficiency of photo electrochemical devices [START_REF] Hu | Bismuth incorporation stabilized a-CsPbl 3 for fully inorganic perovskite solar cells[END_REF][START_REF] Patel | Nitrogen and cobalt co-doped zinc oxide nanowires -viable photoanodes for hydrogen generation via photoelectrochemical water splitting[END_REF][START_REF] Yang | Nitrogen-doped ZnO nanowire arrays for photoelectrochemical water splitting[END_REF][START_REF] Patel | Vertically aligned nitrogen doped (Sn,Nb)O2 nanotubes -robust photoanodes for hydrogen generation by photoelectrochemical water splitting[END_REF][START_REF] Jena | Stabilization of a-CsPbl 3 in ainbient room temperature conditions by incorporating Eu into CsPbl 3[END_REF][START_REF] Wang | Bifunctional ytterbium (III) chloride driven low temperature synthesis of stable a-CsPbl 3 for high-efficiency inorganic perovskite solar cells[END_REF]. Fig. 6a shows the color gradient change for ail our samples after synthesis. We can then assume that the redshift will probably drive to a decrease in the bandgap of the samples. Normalized absorbance spectra performed on pressed powders, after measuring the reflectance only, are shown in Fig. 6b explain the absorption onset redshift observed [START_REF] Mosconi | First-principles modeling of bismuth doping in the MAPbl 3 perovskite[END_REF].

Bismuth can also form clusters and reduce the grain size [START_REF] Sun | Recent advances in bismuth activated photonic materials[END_REF]. The colour change associated with Bi-doping in MAPbBr 3 and a bandgap narrowing was also explained by the change in density of states while introducing Bismuth "impurities", and by the stronger covalent bonding ability of Bi 3 + which is more electronegative than Pb 2+ and also dispose of a non-bonding pair of electrons [START_REF] Al. Abdelhady | Heterovalent dopant incorporation for bandgap and type engineering of perovskite crystals[END_REF]. But as it was stated recently in the literature and was mentioned above in this paper, it is most likely that Bi introduces defect states inside the bandgap [START_REF] Nayak | Impact of Bi 3 + heterovalent doping in organic-inorganic metal halide perovskite crystals[END_REF][START_REF] Patel | Vertically aligned nitrogen doped (Sn,Nb)O2 nanotubes -robust photoanodes for hydrogen generation by photoelectrochemical water splitting[END_REF]. This is the reason of a strong red-shift observed in our case (from -2,7 to 2eV upon 15% Bi-doping), and an enhanced light absorption.

Thin film preparation of Cs2Pb1.xBixCl2I2 would certainly help to verify the optical properties and check the effect of the Bi dopant over the materials band gaps. Still, the structural adjustment and increased light absorption ability of our samples remains worthy to be tested for various opto-electronic applications.

Agingstabili.ty in ambient condilions

In order to track the stability of our samples we measured their XRD patterns up to one month after synthesis for the same amount of sample. Indeed, it is known that halide perovskites are sensitive to air and moisture. This is actually one of the main issues that needs to be solved, with lead replacement, in order to make those materials sustainable in a long term for photovoltaic systems. We noticed that the large peak widths in doped samples were systematically reduced after 7 days in air (Fig. 7). Small impurity peaks of Cs! and PbCl2 appeared also for the larger doping amounts tested (x = 10 and 15%), while for x = 0 and 5%, no extra peaks were observed and the phase remained pure in those latter cases (see supplementary information S3). Afterwards, no major changes in the. XRD patterns were observed after a month of air exposure (see Fig. 7). Ball-milling performed after 7 days in air tend to broaden again the peaks for x = 5% but did not seem to affect the structures of the others, with impurities remaining for the highest x values. The micro strains seem then to have the tendency to be released with time since the peak intensity increases while the full width at half maximum decreases for Bi-doped materials. Indeed, from Table 1 it can be seen that the in crease of intensity (I) and decrease of peak broadening (Hml for the main peak is more important for the samples containing bismuth than for the pristine sample. The rich Bi-doped materials would thus be more air sensitive. FWHM is divided by up to 2 magnitudes of order after one week of air exposure for the doped samples. The structural disorder that appears after the synthesis of Bi-doped materials seems then to rear range after a while. Further experimental measurements such as HRTEM need to be realized on freshly made and aged samples in order to have a better understanding of these strains and rearrangement phenomena.

Conclusions

We were able to obtain pure crystalline powders of 2D-type Ruddlesden-Popper inorganic halide perovskite-derivative phase of Cs2Pb1x Bi x C'2'2 (0 <:: x <:: 0.15) at room temperature within a couple of hours by mechanical synthesis. The substitution of Pb by Bi induces a cell contraction , certainly due to steric effects and to a modification of its chemical environment. Smaller particles and larger microstrains were observed upon increasing the amount of doping agent. A red-shift pro portional to the bismuth content was observed on the powder samples. Structural distortion with Bi-doping and rearrangement upon air expo sure were evidenced by XRD data analysis, and for x <:: 5% the materials can remain pure for at least one month.

  6]. Never theless, organic molecules have some drawbacks, it has a low tolerance to temperature and can be harmful. The use of a totally inorganic system would avoid those main issues. Recently, Li et al. described a new "2D-type" phase, based on the so-called Ruddlesden-Popper structure. It is one of a few structures known at this day that shows a 2D halogenated all-inorganic structure. It consist.s of two dimensional inter-connected octahedral layers separated by either caesium or rubidium cation for all-inorganic lead or tin halide perovskites [7,8]. Cs2PbC'2I2 exhibits a band gap close to 3 eV, not suitable for a large Sun-light energy ab sorption but this can be improved by substitution for solar cell appli cations. Besides, lead clearly needs to be replaced in halide perovskites for environmental and healthcare purposes. Bismuth can be incorpo rated into perovskites to replace lead. Sorne authors claimed for instance that it can stabilize the black alpha phase of CsPbi 3 for fully inorganic perovskite solar cells [9]. Heterovalent doping in lead halide perovskites is not so usual and most of halide perovskites are made in particular atrnosphere conditions and/or upon heating. Li et al. have recently described the synthesis of a new halide poly crystalline phase Cs2PbC12'2 by thermal treatrnent at 500 'C in N2 flame sealed tube over a period of 48 h [7]. We first managed to simplify the synthesis method by being able to obtain this phase in a conventional tube fumace at 350 'C for 12 h in air, nitrogen atrnosphere being not necessary in this case (see supplementary information Sl). However, attempts for doping Cs2PbCl2I2 with bismuth in such conditions were not successful as no change on the XRD patterns were observed and traces of precursors always remained. Besides, bismuth compounds can be vola tile and thermal treatrnents might result in a change of the expected cationic ratio.

Fig. 1 .Fig. 2 .

 12 Fig. 1. a) XRD patterns of Cs2Pb0.9Bi 0.1ClzI2 after different milling times b) XRD patterns of Cs 2 Pb 1 .xBi x Ch1 2 for variable Bi contents.

Fig. 3 .

 3 Fig. 3. SEM images of Cs2Pb1.xBixCh!i samples.

Fig. 4 .

 4 Fig. 4. Variations of microstrains and particles size as a function of bismuth doping in Cs2Pb1-xBixCl2l2. While the particle size tends to decrease upon Bi-doping, Fig. 4 shows that the maximum strains variations (in ° ;ooo) increases as a function of the increased Bi concentration in Cs 2 Pb1-xBixC' 2 I 2 . These strains varia tion tends to saturate close to 90 ° 1000 for the highest x values. Nayak et al. also observed a large peak broadening effect upon doping MAPbBr 3 with bismuth [15]. Non uniform strains or microstrains, usually induced by structural defects or reduced crystalline order, were quantified by analyzing the peak broadening in the diffraction patterns according to the modified Williamson-Hall method.The microstrains and crystal planes distortions consistently increased upon doping in their organic-inorganic 3D perovskite samples. In our work, the milling time was exactly the same for the undoped and 5% Bi-doped sample so it is hard to attribute the peak broadening in the XRD data to this effect alone. Still, microstrains increase with Bi doping while particles size decrease. This common inversed feature can be directly related to the heterovalent doping effect with the introduction of a smaller cation with a higher oxidation state (and possibly cation vacancies) into the 2D perovskite-derivative structure with a general cell decrease and a shortening of the (semi)metal-anion distances, especially in the inner planes of the octahedral layers, inducing particle size decrease and microstrains increase.XRF measurements show that Bi is in the appropriate proportion for each sample (Fig.5). These values were confirmed by EDS analysis (see supplementary information S2). While lead concentration decreases, the

Fig. 5 .

 5 Fig. 5. Lead (red dots) and bismwh (black squares) contents as afunction of the Bi concentration as detennined by XRF measurements. (For interpretation of the references to color in this figure legend, the reader is referred to the Web version of this article.)

Fig. 6 .

 6 Fig. 6. a) Pictures of as-synthesized powders and b) UV-Vis absorbance spectra for x = 0, 5, 10 and 15% (from left to right) determined from reflectance measurement.s on thick powders (without considering the transmittance contribution).

Fig. 7 .

 7 Fig. 7. Ageing study of the XRD patterns for the 10 ato. % Bi-doped Cs2PbCh1 2 sample.

Table 1 Relative Intensity and FWHM (H m ) evolutions for the main (110) peak within a week of air exposure.

 1

	Doping(%)	17/IO	Hm7/Hm0
	0	1.18	0.71
	5	2.00	0.47
	10	1.89	0.47
	15	1.69	0.54

Acknowledgements

We thank Diane Samelor for her assistance in UV-Vis measurements. The International Research Experiences for Undergraduates (iREU) Program and Department of Chemistry at Xavier University of Louisiana in the USA are thanked for giving the opportunity to their student E.J. Marin-Bernardez to go to the CIRIMAT for a couple of months and gain research experience.

Declaration of competing interest

The authors declare that they have no known competing financial interests or persona! relationships that could have appeared to influence the work reported in this paper.

Appendix A. Supplementary data

Supplementary data to this article can be found online at https: / /doi. org/10.1 0l 6/j.matchemphys.2020.122870.


Frédéric Havet
email: fhavet@sophia.inria.fr

Jan Van Den Heuvel

Colin Mcdiarmid

Bruce Reed
email: breed@cs.mcgill.ca

List Colouring Squares of Planar Graphs

Keywords: colouring, list colouring, planar graph, square of a graph coloration, coloration par listes, graphe planaire, carré d'un graphe

)), and indeed this is true for the list chromatic number and for more general classes of graphs.

Introduction

Most of the terminology and notation we use in this paper is standard and can be found in any text book on graph theory ( such as [START_REF] Bondy | Graph Theory with Applications[END_REF] or [START_REF] Diestel | Graph Theory[END_REF] ). All our graphs and multigraphs will be finite. A multigraph can have multiple edges; a graph is supposed to be simple. We will not allow loops.

The degree of a vertex is the number of edges incident with that vertex. We require all colourings, whether we are discussing vertex, edge or list colouring, to be proper : neighbouring objects must receive different colours. We also always assume that colours are integers, which allows us to talk about the "distance" |γ 1 -γ 2 | between two colours γ 1 , γ 2 .

Given a graph G, the chromatic number of G, denoted χ(G), is the minimum number of colours required so that we can properly colour its vertices using those colours. If we colour the edges of G, we get the chromatic index, denoted χ ′ (G). The list chromatic number or choice number ch(G) is the minimum value k, so that if we give each vertex v of G a list L(v) of at least k colours, then we can find a proper colouring in which each vertex gets assigned a colour from its own private list. The list chromatic index is defined analogously for edges. See [START_REF] Woodall | List colourings of graphs[END_REF] for a survey of research on list colouring of graphs.

Colouring the Square of Graphs

Given a graph G, the square of G, denoted G 2 , is the graph with the same vertex set as G and with an edge between all pairs of vertices that have distance at most two in G. If G has maximum degree ∆, then a vertex colouring of its square will need at least ∆ + 1 colours; the greedy algorithm shows it is always possible with ∆ 2 + 1 colours. Diameter two cages such as the 5-cycle, the Petersen graph and the Hoffman-Singleton graph ( see [5, page 239] ) show that there exist graphs that in fact require ∆ 2 + 1 colours, for ∆ = 2, 3, 7, and possibly one for ∆ = 57.

From now on we concentrate on planar graphs. The celebrated Four Colour Theorem by Appel and Haken [START_REF] Appel | Every planar map is four colourable[END_REF][START_REF] Appel | Every planar map is four colourable[END_REF][START_REF] Appel | Every Planar Map is Four Colourable[END_REF] states that χ(G) ≤ 4 for planar graphs. Regarding the chromatic number of the square of a planar graph, Wegner [START_REF] Wegner | Graphs with given diameter and a coloring problem[END_REF] posed the following conjecture ( see also the book of Jensen and Toft [START_REF] Jensen | Graph Coloring Problems[END_REF]Section 2.18] ), suggesting that for planar graphs far less than ∆ 2 + 1 colours suffice.

Conjecture 1.1 ( Wegner [START_REF] Wegner | Graphs with given diameter and a coloring problem[END_REF] ) For a planar graph G of maximum degree ∆,

χ(G 2 ) ≤    7, if ∆ = 3, ∆ + 5, if 4 ≤ ∆ ≤ 7, 3 2 ∆ + 1, if ∆ ≥ 8.
Wegner also gave examples showing that these bounds would be tight. For even ∆ ≥ 8, these examples are sketched in Figure 1. The graph G k consists of three vertices x, y and z together with 3 k -1 additional vertices of degree two, such that z has k common neighbours with x and k common neighbours with y, x and y are connected and have k -1 common neighbours. This graph has maximum degree 2 k and yet all the vertices except z are adjacent in its square. Hence to colour these 3 k + 1 vertices, we need at least 3 k + 1 = 3 2 ∆ + 1 colours. Kostochka and Woodall [START_REF] Kostochka | Choosability conjectures and multicircuits[END_REF] conjectured that for every square of a graph the list chromatic number equals the chromatic number. This conjecture and Wegner's one imply directly the following.

Conjecture 1.2

For a planar graph G of maximum degree ∆, Wegner also showed that if G is a planar graph with ∆ = 3, then G 2 can be 8-coloured. Very recently, Thomassen [START_REF] Thomassen | The square of a planar cubic graph is 7-colorable[END_REF] established Wegner's conjecture for ∆ = 3, and Cranston and Kim [START_REF] Cranston | List-coloring the square of a subcubic graph[END_REF] showed that the square of every connected graph ( not necessarily planar ) which is subcubic ( i.e., with ∆ ≤ 3 ) is 8choosable, except for the Petersen graph. However, the 7-choosability of the square of subcubic planar graphs is still open.

ch(G 2 ) ≤    7, if ∆ = 3, ∆ + 5, if 4 ≤ ∆ ≤ 7,
The first upper bound on χ(G 2 ) for planar graphs in terms of ∆, χ(G 2 ) ≤ 8 ∆ -22, was implicit in the work of Jonas [START_REF] Jonas | Graph coloring analogues with a condition at distance two : L(2, 1)-labelings and list λ-labelings[END_REF]. ( The results in [START_REF] Jonas | Graph coloring analogues with a condition at distance two : L(2, 1)-labelings and list λ-labelings[END_REF] deal with L(2, 1)-labellings, see below, but the proofs are easily seen to be applicable to colouring the square of graphs as well. ) This bound was later improved by Wong [START_REF] Wong | Colouring graphs with respect to distance[END_REF] to χ(G 2 ) ≤ 3 ∆ + 5 and then by Van den Heuvel and McGuinness [START_REF] Van Den Heuvel | Coloring the square of a planar graph[END_REF] to χ(G 2 ) ≤ 2 ∆ + 25. Better bounds were then obtained for large values of ∆. It was shown that χ(G 2 ) ≤ 9 5 ∆ +1 for ∆ ≥ 750 by Agnarsson and Halldórsson [START_REF] Agnarsson | Coloring powers of planar graphs[END_REF], and the same bound for ∆ ≥ 47 by Borodin et al. [START_REF] Borodin | Minimal degrees and chromatic numbers of squares of planar graphs (in Russian)[END_REF]. Finally, the asymptotically best known upper bound so far has been obtained by Molloy and Salavatipour [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF] as a special case of Theorem 1.7 below.

Theorem 1.3 ( Molloy and Salavatipour [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF] ) For a planar graph G, χ(G 2 ) ≤ 5 3 ∆ + 78.

As mentioned in [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF], the constant 78 can be reduced for sufficiently large ∆. For example, it was improved to 24 when ∆ ≥ 241.

In this paper we prove the following theorem.

Theorem 1.4

The square of every planar graph G of maximum degree ∆ has list chromatic number at most (1+o(1)) 3 2 ∆. Moreover, given lists of this size, there is a proper colouring in which the colours on every pair of adjacent vertices of G differ by at least ∆ 1/4 .

A more precise statement is as follows. For each ǫ > 0, there is a ∆ ǫ such that for every ∆ ≥ ∆ ǫ we have : for every planar graph G of maximum degree at most ∆, and for all vertex lists each of size at least 3 2 + ǫ ∆, there is a proper list colouring, with the further property that the colours on every pair of adjacent vertices of G differ by at least ∆ 1/4 .

The o(1) term in the theorem is as ∆ -→ ∞. The first order term 3 2 ∆ in Theorem 1.5 is best possible, as the examples in Figure 1 show. On the other hand, the term ∆ 1/4 is probably far from best INRIA possible; it was chosen to keep the proof simple. The main point, to our minds, is that this parameter tends to infinity as ∆ -→ ∞.

In fact, we prove a more general theorem. Let G be a graph with vertex set V (G) and edge set E(G). For U, W ⊆ V (G) we define e(U, W ) = |{ uw ∈ E(G) | u ∈ U, w ∈ W }|. Note that this means that any edge between two vertices in U ∩ W is counted twice. A family F of graphs is called nice if it is closed under taking minors and the following condition holds : there exists an absolute constant β F such that for any graph G ∈ F and any vertex set B ⊆ V (G), the set A of vertices in V \ B which have at least three neighbours in B satisfies e(A, B) ≤ β F |B|. Note that this condition means that a nice class can not be the class of all graphs.

Theorem 1.5 Let F be a nice family of graphs. The square of every graph G in F of maximum degree ∆ has list chromatic number at most (1 + o(1)) 3 2 ∆. Moreover, given lists of this size, there is a proper colouring in which the colours on every pair of adjacent vertices of G differ by at least ∆ 1/4 . It is not difficult to prove that planar graphs form a nice family ( see Section 2 ). But there are many other families which also are nice, such as graphs embeddable on a given surface, or K 3,k -minor free graphs for a fixed k.

Note that K 3,7 has K 4 as a minor, and so K 4 -minor free graphs ( that is, series-parallel graphs ) form a nice class. Lih, Wang and Zhu [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF] showed that the square of K 4 -minor free graphs with maximum degree ∆ has chromatic number at most 3 2 ∆ + 1 if ∆ ≥ 4 and ∆ + 3 if ∆ = 2, 3. The same bounds, but then for the list chromatic number of K 4 -minor free graphs, were proved by Hetherington and Woodall [START_REF] Hetherington | List-colouring the square of a K 4 -minor-free graph[END_REF].

L(p, q)-Labellings of Graphs

Vertex colourings of squares of graphs can be considered a special case of a more general concept : L(p, q)labellings of graphs. This topic takes some of its inspiration from so-called channel assignment problems. The channel assignment problem in radio or cellular phone networks is the following : we need to assign radio frequency channels to transmitters ( each station gets one channel which corresponds to an integer ). In order to avoid interference, if two stations are very close, then the separation of the channels assigned to them has to be large enough. Moreover, if two stations are close ( but not very close ), then they must also receive channels that are sufficiently apart.

Such problem may be modelled by L(p, q)-labellings of a graph G, where p and q are non-negative integers. The vertices of this graph correspond to the transmitters and two vertices are linked by an edge if they are very close. Two vertices are then considered close if they are at distance two in the graph. Let dist(u, v) denote the distance between the two vertices u and v. An L(p, q)-labelling of G is an integer assignment f to the vertex set V (G) such that :

• |f (u) -f (v)| ≥ p, if dist(u, v) = 1, and • |f (u) -f (v)| ≥ q, if dist(u, v) = 2.
It is natural to assume that p ≥ q.

The span of f is the difference between the largest and the smallest labels of f plus one. The λ p,q -number of G, denoted by λ p,q (G), is the minimum span over all L(p, q)-labellings of G.

The problem of determining λ p,q (G) has been studied for some specific classes of graphs ( see the survey of Yeh [START_REF] Yeh | A survey on labeling graphs with a condition at distance two[END_REF] ). Generalisations of L(p, q)-labellings in which for each i ≥ 1, a minimum gap of p i is required for channels assigned to vertices at distance i, have also been studied ( see for example [START_REF] Král | Channel assignment problem with variable weights[END_REF] or [START_REF] Liu | Multilevel distance labelings for paths and cycles[END_REF] ). Moreover, very often, because of technical reasons or dynamicity, the set of channels available varies from transmitter to transmitter. Therefore one has to consider the list version of L(p, q)-labellings. A k-list assignment L of a graph is a function which assigns to each vertex v of the graph a list L(v) of k prescribed integers. Given a graph G, the list λ p,q -number, denoted λ l p,q (G) is the smallest integer k such that, for every k-list assignment L of G, there exists an L(p, q)-labelling f such that f (v) ∈ L(v) for every vertex v. Surprisingly, list L(p, q)-labellings have received very little attention and appear only very recently in the literature [START_REF] Kohl | List version of L(d, s)-labelings[END_REF]. However, some of the proofs for L(p, q)-labellings also work for list L(p, q)-labellings.

Note that L(1, 0)-labellings of G correspond to ordinary vertex colourings of G and L(1, 1)-labellings of G to vertex colourings of the square of G. So we have that

λ 1,0 (G) = χ(G), λ l 1,0 (G) = ch(G), λ 1,1 (G) = χ(G 2 ), and λ l 1,1 (G) = ch(G 2
). It is well known that for a graph G with clique number ω ( the size of a maximum clique in G ) and maximum degree ∆ we have ω ≤ χ(G) ≤ ch(G) ≤ ∆ + 1. Similar easy inequalities may be obtained for L(p, q)-labellings :

q ω(G 2 ) -q + 1 ≤ λ p,q (G) ≤ λ l p,q (G) ≤ p ∆(G 2 ) + 1.
As ω(G 2 ) ≥ ∆(G) + 1, the previous inequality gives λ p,q (G) ≥ q ∆ + 1. However, a straightforward argument shows that in fact we must have λ p,q (G) ≥ q ∆ + p -q + 1. In the same way, ∆(G

2 ) ≤ ∆ 2 (G) so λ l p,q (G) ≤ p ∆ 2 (G) + 1.
The "many-passes" greedy algorithm ( see [START_REF] Mcdiarmid | On the span in channel assigment problems : bounds, computing and counting[END_REF] ) gives the alternative bound

λ l p,q (G) ≤ q ∆ (∆ -1) + p ∆ + 1 = q ∆ 2 (G) + (p -q) ∆(G) + 1.
Taking an L(⌈p/k⌉, ⌈q/k⌉)-labelling and multiplying each label by k, for some positive integer k, we obtain an L(p, q)-labelling. We can extend this easy observation.

Proposition 1.6

For all graphs G and positive integers p and q, we have λ l p,q (G) ≤ q λ l t,1 (G) where t = p -1 q + 1.

To prove this, consider lists

L(v) for v ∈ V (G) each of size at least q • λ l t,1 (G). For each v let L(v) = { ⌈k/q⌉ | k ∈ L(v) }, and note that | L(v)| ≥ |L(v)|/q ≥ λ l t,1 (G).
Thus there is a colouring f for G such that we always have

f (v) ∈ L(v), | f (u) -f (v)| ≥ t if dist(u, v) = 1 and f (u) = f (v) if dist(u, v) = 2. For each v let f (v) be any number in L(v) such that ⌈f (v)/q⌉ = f (v). It suffices to show that f is an L(p, q)-labelling for G. But clearly f (u) = f (v) if dist(u, v) = 2, and if dist(u, v) = 1, then |f (u) -f (v)| ≥ q | f (u) -f (v)| -1 + 1 ≥ q (t -1) + 1 ≥ p.
Because for many large-scale networks, the transmitters are laid out on the surface of the earth, L(p, q)-labellings of planar graphs are of particular interest. There are planar graphs for which λ p,q ≥ 3 2 q ∆ + c(p, q), where c(p, q) is a constant depending on p and q. We already saw some of those examples in Figure 1. The graph G k has maximum degree 2 k and yet its square contains a clique with 3 k + 1 vertices ( all the vertices except z ). Labelling the vertices in the clique already requires a span of at least q • 3 k + 1 = 3 2 q ∆ + 1. A first upper bound on λ p,q (G), for planar graphs G and positive integers p ≥ q was proved by Van den Heuvel and McGuinness [START_REF] Van Den Heuvel | Coloring the square of a planar graph[END_REF] : λ p,q (G) ≤ 2 (2 q -1) ∆ + 10 p + 38 q -24. Molloy and Salavatipour [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF] improved this bound by showing the following. Theorem 1.7 ( Molloy and Salavatipour [START_REF] Molloy | A bound on the chromatic number of the square of a planar graph[END_REF] ) For a planar graph G and positive integers p, q, λ p,q (G) ≤ q 5 3 ∆ + 18 p + 77 q -18.

INRIA

Moreover, they described an O(n 2 ) time algorithm for finding an L(p, q)-labelling whose span is at most the bound in their theorem. As a corollary to our main result Theorem 1.5 we get that, for any fixed p and every nice family F of graphs, we have λ l p,1 (G) ≤ (1 + o(1)) 3 2 ∆(G) for G ∈ F. Together with Proposition 1.6, this yields :

Corollary 1.8
Let F be a nice family of graphs and let p and q be positive integers. Then for graphs G in F we have

λ l p,q (G) ≤ (1 + o(1)) 3 2 q ∆(G).
Note that the examples discussed earlier show that for each positive integer q the factor 3 2 q is optimal.

2 Nice Families of Graphs

The following proposition shows that the family of planar graphs is nice.

F is K 3,k -minor free if k > β F .
Next suppose that every graph in F is K 3,k -minor free. We want to prove that F is nice. Note that by Theorem 2.2, the average degree of a K 3,k -minor free graph is bounded by some integral constant C k .

Let G ∈ F, B a set of vertices of G, and A the set of vertices in V \B having at least three neighbours in B. Construct a graph H with vertex set B as follows : For each vertex of A, one after another, if two of its neighbours in B are not linked yet in H, choose a pair of those non-adjacent neighbours and add an edge between them.

Let A ′ ⊆ A be the set of vertices for which an edge has been added to H, and set

A ′′ = A \ A ′ . Then H is K 3,k -minor free because G was, and hence |A ′ | = |E(H)| ≤ 1 2 C k |B|.
Now for every vertex a ∈ A ′′ , the neighbours of a in B form a clique in H ( otherwise we would have used a to link two of its neighbours in B ). Moreover, k vertices of A ′′ may not be adjacent to the same triangle of H, otherwise G would contain a K 3,k -minor. Hence

|A ′′ | is at most k -1 times the number of triangles in H, which is at most C k 2 |B| by Corollary 2.3. We find that |A ′′ | ≤ (k -1) C k 2
|B|, and hence

|A| = |A ′ | + |A ′′ | ≤ 1 2 C k + (k -1) C k 2 |B|. Since the subgraph of G induced on A ∪ B is K 3,k -minor free, there are at most 1 2 C k (|A| + |B|) edges between A and B; that is, at most 1 2 C k 1 2 C k + (k -1) C k 2 + 1 |B|.
3 Sketch of the proof of Theorem 1.5

To prove Theorem 1.5, for a fixed nice family F, we need to show that for every ǫ > 0, there is a ∆ ǫ such that for every ∆ ≥ ∆ ǫ we have : for every graph G ∈ F of maximum degree at most ∆, given lists of size c ǫ = 3 2 + ǫ ∆ for each vertex v of G, we can find the desired colouring. We proceed by induction on the number of vertices of G. Our proof is a recursive algorithm. In each iteration, we split off a set R of vertices of the graph which are easy to handle, recursively colour G 2 -R ( which we can do by the induction hypothesis ), and then extend this colouring to the vertices of R. In extending the colouring, we must ensure that no vertex v of R receives a colour used on a vertex of V -R which is adjacent to v in G 2 . Thus, we modify the list L(v) of colours available for v by deleting those which appear on such neighbours.

We note that (G -R) 2 need not be equal to G 2 -R, as there may be non-adjacent vertices of G -R with a common neighbour in R but no common neighbour in G -R. When choosing R we need to ensure that we can construct a graph

G 1 in F on V -R such that G 2 -R ⊆ G 2 1 .
We also need to ensure that the connections between R and V -R are limited, so that the modified lists used when list colouring G 2 [R] are still reasonably large. Finally, we will want G 2 [R] to have a simple structure so that we can prove that we can list colour it as desired.

We begin with a simple example of such a set R. We say a vertex v of G is removable if it has at most ∆ 1/4 neighbours in G and at most two neighbours in G which have degree at least ∆ 1/4 . We note that if v is a removable vertex with exactly two neighbours x and y, then setting G 1 = G -v + e, where e is an edge between x and y, we have that

G 1 is in F and G 2 -v ⊆ G 2
1 . On the other hand, if v is a removable vertex with at least three neighbours, then it must have a neighbour w of degree at most ∆ 1/4 . In this case, the graph G 2 obtained from G -v by adding an edge from w to every other neighbour of v

INRIA in G is a graph of maximum degree at most ∆ such that G 2 -v ⊆ G 2 2
. Furthermore, G 2 ∈ F as it is obtained from G by contracting the edge wv.

Thus, for any removable vertex v, we can recursively list colour G 2 -v using our algorithm. If, in addition, v has at most c ǫ -1 -2 ∆ 1/2 neighbours in G 2 , then our bound on d G 2 (v) ensures that there will be a colour in L(v) which appears on no vertex adjacent to v in G 2 and is not within ∆ 1/4 of any colour assigned to a neighbour of v in G. To complete the colouring we give v any such colour.

The above remarks show that no minimal counterexample to our theorem can contain a removable vertex of low degree in G 2 . We are about to describe another, more complicated, reduction we will use. It relies on the following easy result.

Lemma 3.1 If R is a set of removable vertices of G, then there is a graph G 1 ∈ F with vertex set V -R and maximum degree at most ∆ such that G 2 -R is a subgraph of G 2 1 .
Proof For each v ∈ R of degree at least three in V -R, choose a neighbour of v of degree less than ∆ 1/4 onto which we will contract v. Add an edge between the two neighbours of any vertex in R with exactly two neighbours in V -R ( if they are not already adjacent ). The degree of a vertex x in the resultant graph G 1 is at most the maximum of ∆ 1/2 or d G (x).

For any multigraph H, we let H * be the graph obtained from H by subdividing each edge exactly once.

For each edge e of H, we let e * be the vertex of H * which we placed in the middle of e and we let E * be the set of all such vertices. We call this set of vertices corresponding to the edges of H the core of H * . A removable copy of H * is a subgraph of G isomorphic to H * such that the vertices of G corresponding to the vertices of the core of H * are removable, and each vertex of H * arising from H has degree at least ∆ 1/4 .

Note that the subgraph J of G 2 induced by the core of some copy of H * in G contains a subgraph isomorphic to L(H), the line graph of H. So the list chromatic number of J is at least the list chromatic number of L(H). If the copy is removable, then removing the edges of this copy of L(H) from J yields a graph in which the vertices in the core have degree at most ∆ 1/2 . Thus, the key to list colouring J will be to list colour L(H). Fortunately, list colouring line graphs is much easier than list colouring arbitrary graphs ( see e.g. [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF][START_REF] Kayll | Asymptotically good choice numbers of multigraphs[END_REF][START_REF] Molloy | Graph colouring and the probabilistic method[END_REF] ). In particular, using a sophisticated argument due to Kahn [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF], we can prove the following lemma which specifies certain sets of removable vertices which we can use to perform reductions.

Lemma 3.2

Suppose R is the core of a removable copy of H * in G, for some multigraph H, such that for any set X of vertices of H and corresponding set X * of vertices of the copy of H * , we have that the sum of the degrees in G -R of the vertices in X * exceeds the number of edges of H out of X by at most ǫ |X| ∆ 10 .

Then, any c ǫ -colouring of G 2 -R can be extended to a c ǫ -colouring of G 2 .

The following lemma shows that we will indeed be able to find a removable set of vertices which we can use to perform a reduction.

Lemma 3.3

For any ε > 0, there exists ∆ ε such that any graph G ∈ F of maximum degree ∆ ≥ ∆ ε contains at least one of the following :

(A) a removable vertex v which has degree less than 3 2 ∆ + ∆ 1/2 in G 2 , or (B) a removable copy of H * with core R, for some multigraph H which contains an edge and is such that for any set X of vertices of H we have : the sum of the degrees in G -R of the vertices in X exceeds the number of edges of H out of X by at most |X| ∆ 9/10 .

Combining Lemmas 3.1, 3.2, and 3.3 yields Theorem 1.5. Thus, we need only prove the last two of these lemmas. The proof of Lemma 3.3 is given in the next section. The proof of Lemma 3.2 is much more complicated and forms the bulk of the paper. We follow the approach developed by Kahn [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF] for his proof that the list chromatic index of a multigraph is asymptotically equal to its fractional chromatic number. We need to modify the proof so it can handle our situation in which we have a graph which is slightly more than a line graph and in which we have lists with fewer colours than he permitted. We defer any further discussion to Section 5.

Finding a Reduction

In this section we prove Lemma 3.3. Throughout the section we assume that F is a nice family of graphs. Since F is minor-closed and not the class of all graphs, there exists a graph H so that every graph in F is H-minor free. By Theorem 2.2, every graph in F has average degree at most C F for some constant C F . Let G be a graph in F with vertex set V and maximum degree at most ∆. We set n = |V |. We let B be the set of vertices of degree exceeding ∆ 1/4 . Since the average degree of G is at most

C F , we have |B| < C F n ∆ 1/4
. Then from property (c) of the definition of nice family, we obtain that G contains a set R 0 of at least n -O n ∆ 1/4 removable vertices. We note that if a vertex in R 0 sees a vertex in B of degree less than 1 2 ∆ or sees at most one vertex in B, then its total degree in the square is at most 3 2 ∆ + ∆ 1/2 and conclusion (A) of Lemma 3.3 holds. So, we can assume this is not the case.

We let V 0 be the set of vertices of G which have degree at least 1 2 ∆. Since every vertex in R 0 has exactly two neighbours in V 0 , the sum of the degrees of the vertices in V 0 is at least 2 |R 0 |. This gives

|V 0 | ≥ 2 n ∆ -O n ∆ 5/4
. We let S 0 be the set of vertices in V 0 which see more than ∆ 7/8 vertices of V \ R 0 . Since the total number of edges within

V \ R 0 is O n ∆ 1/4 , we find that |S 0 | = O n ∆ 9/8 . We set V 1 = V 0 \ S 0 and note |V 1 | ≥ 2 n ∆ -O n ∆ 9/8
. We can conclude that

|V 1 | ≥ n ∆ , for large enough ∆. ( 1
)
We let R 1 be the set of vertices in R 0 adjacent to ( exactly ) two vertices in V 1 . So every vertex in R 0 \ R 1 has one or two neighbours in S 0 . By our bound on the size of S 0 this means

|R 0 \ R 1 | = O n ∆ 1/8
and hence

|R 1 | = n -O n ∆ 1/8 . By our choice of S 0 we have that e(V 1 , V \ R 0 ) ≤ ∆ 7/8 |V 1 |. Since every vertex in R 0 \ R 1 has at most one neighbour in V 1 , we have e(V 1 , R 0 \ R 1 ) ≤ |R 0 \ R 1 | = O n ∆ 1/8 ≤ O(∆ 7/8 ) |V 1 | ( here we used (1) ). We obtain e(V 1 , V \ R 1 ) = e(V 1 , V \ R 0 ) + e(V 1 , R 0 \ R 1 ) ≤ O(∆ 7/8 ) |V 1 |.

INRIA

We let F 1 be the bipartite graph formed by the edges between the vertices of R 1 and the vertices of V 1 . We remind the reader that each vertex of R 1 has degree two in this graph. We let H 1 be the multigraph with vertex set V 1 from which F 1 is obtained by subdividing each edge exactly once.

We check if F 1 is a removable copy of H 1 as in (B). The only reason that it might not be is that there is some subset Z ⊆ V 1 of vertices of H 1 such that the sum of the degrees in G -R 1 of the vertices in Z exceeds the number of edges of H 1 out of Z by more than |Z| ∆ 9/10 . In other words we have

e(Z, V \ R 1 ) = v∈Z d G-R1 (v) > e H1 (Z, V 1 \ Z) + |Z| ∆ 9/10 . (2)
In this case, we set

V 2 = V 1 \ Z, let R 2 be the subset of R 1 containing no neighbours in Z, let F 2 be
the bipartite subgraph of G induced by the edges between the vertices of R 2 and the vertices of V 2 , and let H 2 be the graph on V 2 from which F 2 is obtained by subdividing each edge exactly once. We note that the edges from

V 2 to V \ R 2 are the edges from V 1 to V \ R 1 minus the edges from Z to V \ R 1 , plus the edges from V 2 to vertices of R 1 \ R 2 : e(V 2 , V \ R 2 ) = e(V 1 \ Z, V \ R 2 ) = e(V 1 , V \ R 1 ) -e(Z, V \ R 1 ) + e(V 2 , R 1 \ R 2 ). For every vertex v in R 1 \ R 2 adjacent to a vertex in V 2 , there also is a vertex in Z it is adjacent to. Hence e(V 2 , R 1 \ R 2 ) is precisely the number of edges of H 1 out of Z : e(V 2 , R 1 \ R 2 ) = e H1 (Z, V 1 \ Z). Using (2) gives e(V 1 , V \ R 1 ) > e(V 2 , V \ R 2 ) + |Z| ∆ 9/10 . Now we check if F 2 is a removable copy of H 2 as in (B).
If not we can proceed in the same fashion deleting a set of vertices from V 2 and R 2 to obtain a new graph.

At some point this process stops. We have constructed new sets V 1 , R 1 , V 2 , R 2 , . . . , . . . V i , R i . We must show that R i = ∅ since then the corresponding graph H i has at least one edge. Letting Z ′ be V 1 \ V i , we know that the number of edges from V 1 to V \ R 1 exceeds the number of edges from V i to V \ R i by at least |Z ′ | ∆ 9/10 . Using the estimate of e(V 1 , V \ R 1 ) from above, this implies

|Z ′ | ≤ e(V 1 , V \ R 1 ) -e(V i , V \ R i ) ∆ 9/10 ≤ O(∆ 7/8 ) |V 1 | ∆ 9/10 = |V 1 | O(∆ -1/40 ),
and hence

|V i | ≥ |V 1 | (1 -O(∆ -1/40 )), which also gives |V 1 | ≤ (1 + O(∆ -1/40 )) |V i |. Since V i is a subset of V 1 , we know that e(V i , V \ R 0 ) ≤ ∆ 7/8 |V i |. Using the earlier estimate of e(V 1 , R 0 \ R 1 ) we also know e(V i , R 0 \ R 1 ) ≤ e(V 1 , R 0 \ R 1 ) ≤ O(∆ 7/8 ) |V 1 | ≤ O(∆ 7/8 ) |V i |.
Finally, for each edge between V i and R 1 \ R i , we have at least one edge between R 1 \ R i and Z ′ as well. We find

e(V i , R 1 \ R i ) ≤ |Z ′ | ∆ ≤ |V 1 | O(∆ 39/40 ) ≤ O(∆ 39/40 ) |V i |.
Combining these estimates we obtain

e(V i , V \ R i ) = e(V i , V \ R 0 ) + e(V i , R 0 \ R 1 ) + e(V i , R 1 \ R i ) ≤ O(∆ 39/40 ) |V i |.
But each vertex in V i has degree at least 1 2 ∆. This means that e(V i , R i ) > 0 for large enough ∆. In particular, it follows that R i is non-empty. Thus, H i contains an edge. We have shown that (B) holds.

This completes the proof of Lemma 3.3.

Reducing using Line Graphs

In this section we focus our attention on multigraphs. We always assume that H is a multigraph with vertex set V and maximum degree ∆. We abuse notation by writing e = uv when we want to say that e is an edge with endvertices u and v ( there can be many such edges ). For U, W ⊆ V , define e(U, W ) = |{ e = uw | u ∈ U, w ∈ W }|. As before this means that any edge with two endvertices in U ∩ W is counted twice.

In this section we prove the following result and then derive Lemma 3.2 as a corollary.

Lemma 5.1

For every ǫ > 0 there is a ∆ ǫ such that the following holds for all ∆ ≥ ∆ ǫ . Let H be a multigraph with vertex set V and maximum degree at most ∆. For each edge we are given a list L(e) of acceptable colours. Additionally, J 1 is a graph on E(H) of maximum degree at most ∆ 1/2 and J 2 is a graph on E(H) of maximum degree at most ∆ 1/4 . Suppose the following two conditions are satisfied.

1.

For every edge e with endvertices v and w :

|L(e)| = 3 2 + ǫ ∆ -(∆ -d(v)) -(∆ -d(w)) -3 ∆ 1/2 .

2.

For any set X of an odd number of vertices of H :

v∈X (∆ -d(v)) -e(X, V \ X) ≤ ǫ |X| ∆ 10 .
Then we can find a proper colouring of L(H) such that any pair of edges of H joined by an edge of J 1 receive different colours, and the colours of the endvertices of any edge of J 2 differ by at least ∆ 1/4 .

Remark 5.2

Condition 2 of the previous lemma applied to the set X = {v} implies that for any vertex v, d(v) ≥ 1 2 -1 20 ǫ ∆. By taking ∆ large enough this implies that for any edge e the right hand side in Condition 1 is positive.

To prove the lemma, we will analyse a procedure which chooses matchings of each colour at random in H. Basically, for each colour γ and edge e with γ ∈ L(e), we would like the probability that e is in the random matching M γ of colour γ to be near |L(e)| -1 . Thus the expected number of matchings chosen which contain e will be near one. By using the Lovász Local Lemma to guide these choices carefully, we can actually ensure that each edge is indeed chosen by one matching. Before we describe our approach any further, we state the Local Lemma, and restate our problem in terms of line graphs.

The Lopsided Local Lemma

The Lovász Local Lemma is a powerful tool which allows one to prove results about the global structure of an object using a local analysis. There are many variants of this lemma ( see e.g. [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]Chapters 4 and 8] ). We will use the following variant, which can be found in [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF].

Lemma 5.3 ( Erdős and Lovász [START_REF] Erdős | Problems and results on 3-chromatic hypergraphs and some related questions[END_REF] ) Suppose that B is a set of ( bad ) events in a probability space Ω. Suppose further that there are p and d such that we have :

1.
for every event B in B, there is a subset S B of B of size at most d, such that the conditional probability of B, given any conjunction of occurrences or non-occurrences of events in B \ S B , is at most p, and

INRIA 2. e p d < 1. 1
Then with positive probability, none of the events in B occur.

We will analyse the behaviour of the set of random matchings we choose using this lemma. When we do so, the bad events we consider will typically be indexed by the edges of H and for an event B e indexed by e, the events in S Be will typically be events indexed by an edge w within a specified distance d of e in H. To be able to apply the lemma, we need to ensure that conditioning on the edges chosen by a matching in one part of the multigraph will not have too great an effect on the edges it picks in distant parts of the multigraph.

Probability Distributions on Matchings

For a probability distribution p, defined on the matchings of a multigraph H, we let x p (e) be the probability that e is in a matching chosen according to p. We call the value of x p (e) the marginal of p at e. The vector x p = (x p (e)) indexed by the edges e is called the marginal of p. We are interested in finding probability distributions where the marginal at e is |L(e)| -1 . We are actually interested in using special types of probability distributions on the matchings of H which have independence properties which will allow us to apply the Local Lemma. Most of the material presented in this section may be found in [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]Chapter 22].

A probability distribution p on the matchings of H is hard-core if it is obtained by associating a nonnegative real λ p (e) to each edge e of H so that the probability that we pick a matching M is proportional to e∈M λ p (e). I.e., setting λ p (M ) = e∈M λ p (e) and letting M(H) be the set of matchings of H, we have

p(M ) = λ p (M ) N ∈M(H)
λ p (N ) .

We call the values λ p (e) the activities of p.

Our interest in these special distributions is motivated by the following result which makes them suitable for use with the Local Lemma.

Suppose that we are choosing a random matching M from some probability distribution. For a vertex v we say that an event Q is t-distant from v if it is completely determined by the choice of all the matching edges at distance t or greater from v. We say that an event is t-distant from an edge e if it is t-distant from both ends of e. Lemma 5.4 ( Kahn and Kayll [START_REF] Kahn | On the stochastic independence properties of hard-core distributions[END_REF] )

Fix K > 0 and 0 < ǫ < 1. Let t = t ǫ = 8 (K + 1) 2 ǫ + 2.
Consider a multigraph H and hard-core distribution p whose activities satisfy for all x ∈ V (H) : e∋x λ p (e) < K. If we choose a matching M according to p, then the following is true.

• For any edge e and event Q which is t-distant from e,

(1 -ǫ) Pr(e ∈ M ) ≤ Pr(e ∈ M | Q) ≤ (1 + ǫ) Pr(e ∈ M ).
This result shows that hard-core probability distributions with bounded activities are amenable to analysis via the Local Lemma. Our next step is to prove that there are such probability distributions with the marginals we desire.

Finding an arbitrary probability distribution on the matchings of H with marginals x is equivalent to expressing x as a convex combination of incidence vectors of matchings of H. So, we can use a seminal result due to Edmonds [START_REF] Edmonds | Maximum matching and a polyhedron with 0, 1-vertices[END_REF] to understand for which x this is possible.

The matching polytope MP(H) is the set of non-negative vectors x indexed by the edges of H which are convex combination of incidence vectors of matchings.

Theorem 5.5 ( Edmonds [9] ) ( Characterisation of the Matching Polytope ) A non-negative vector x indexed by the edges of H is in MP(H) if and only if 1.

for every vertex v of H :

e∋v x e ≤ 1, and
2. for all F ⊆ H with |V (F )| ≥ 3 odd : e∈E(F )
x e ≤ 1 2 (|V (F )| -1).

Remark 5.6

It is easy to see Conditions 1 and 2 are necessary as they are satisfied by all the incidence vectors of matchings and hence by all their convex combinations. It is proving that they are sufficient which is difficult.

It turns out that we can choose a hard-core distribution with marginals x provided all of the inequalities are strict. Lemma 5.7 ( Lee [START_REF] Lee | Some recent results on convex polytopes[END_REF]; Rabinovitch, Sinclair and Widgerson [START_REF] Rabinovitch | Quadratic dynamical systems[END_REF] ) There is a hard-core distribution with marginals x if and only if 1.

for every vertex v of H : We are interested in hard-core distributions where the λ p are bounded because, as we saw above, they have the independence properties we need. It turns out that to ensure this is the case, we need to stay slightly further away from the boundary of the Matching Polytope.

Lemma 5.8 ( Kahn and Kayll [START_REF] Kahn | On the stochastic independence properties of hard-core distributions[END_REF] ) For all δ, 0 < δ < 1, there is a β such that, for each multigraph H, if p is a hard-core distribution in (1 -δ)MP(H), then 1.

for every edge e of H : λ p (e) < β x p (e), and 2.

for every vertex v of H : e∋v λ p (e) < β.

To complete this subsection, we show that the marginals for which we need to construct probability distributions are indeed well inside the Matching Polytope.

Lemma 5.9 Let 0 < ǫ ≤ 1/4. Then there is a ∆ ǫ such that for every ∆ ≥ ∆ ǫ the following holds. Let H be a multigraph with vertex set V and maximum degree at most ∆, and for each edge e let L(e) be a list of acceptable colours. Suppose the following conditions are satisfied :

1.

For every edge e with endvertices v and w :

|L(e)| ≥ 3 2 + ǫ ∆ -(∆ -d(v)) -(∆ -d(w)) -3 ∆ 1/2 . INRIA 2.
For any set X of an odd number of vertices of H :

v∈X (∆ -d(v)) -e(X, V \ X) ≤ ǫ |X| ∆ 10 .
Then, the vector obtained by setting

x e = 1 + 1 2 ǫ |L(e)|
for each edge e of H is in the Matching Polytope of H.

Proof We need only show that x satisfies the inequalities in Edmond's Characterisation of the Matching Polytope, Theorem 5.5. Whenever an inequality requires ∆ to be large enough, we use "≥ * ".

To begin, we note that the second condition of the lemma implies that every vertex w of H has degree at least 1 2 -1 20 ǫ ∆. Thus, for any edge e = vw of H, the first condition of the lemma implies

|L(e)| ≥ d(v) + 19 20 ǫ ∆ -3 ∆ 1/2 ≥ * d(v) + 3 4 ǫ ∆ ≥ 1 + 3 4 ǫ d(v).
We shall use this fact repeatedly throughout the proof.

As the first application, we note that we have for all v ∈ V , e∋v x e < 1. This shows that the first inequality in the characterisation in Theorem 5.5 is satisfied.

Consider next a subgraph F of H with a vertex set X containing three vertices x, y, z, and with α ∆ edges. Applying the second condition gives

3 ∆ -d(x) -d(y) -d(z) ≤ e(X, V \ X) + 3 10 ǫ ∆. Since we also have 3 ∆ -d(x) -d(y) -d(z) = 3 ∆ -2 α ∆ -e(X, V \ X), we obtain 3 ∆ -d(x) -d(y) -d(z) ≤ 3 + 3 10 ǫ 2 -α ∆,
which we can rewrite as

3 2 ∆ ≥ 3 ∆ -d(x) -d(y) -d(z) - 3 20 ǫ ∆ + α ∆.
Substituting this into the first condition of the lemma yields that for any edge e = uv in F :

|L(e)| ≥ ∆ + (d(u) + d(v) -d(x) -d(y) -d(z)) + α + 17 20 ǫ ∆ -3 ∆ 1/2 .
Since ∆ -d(w) is non-negative for any w in X, this yields

|L(e)| ≥ α + 17 20 ǫ ∆ -3 ∆ 1/2 ≥ * α + 3 4 ǫ ∆.
Since α ≤ 3 2 , this gives that for any edge e in F ,

x e ≤ 1 + 1 2 ǫ α + 3 4 ǫ ∆ ≤ 1 α ∆ . We can conclude e∈E(F ) x e ≤ (α ∆) • 1 α ∆ = 1
. This shows that the second inequality in the Characterisation of the Matching Polytope is satisfied for all X with three vertices.

Next consider any subgraph F of H with vertex set X, where |X| ≥ 5 is odd. For each vertex v of F we let E(v) be the set of edges of F incident to v. We partition the vertices of F into a set B of vertices of degree at least 3 4 ∆ and a set S of vertices of degree less than 3 4 ∆. Case 1 : There is a vertex of B whose degree is not more than 7 8 ∆ or a vertex of S whose degree is not more than 5 8 ∆.

Recall first that for any edge e = vw, |L(e

)| ≥ 1 + 3 4 ǫ d(v), so x e ≤ 1 d(v)
. Moreover, for w ∈ B, applying the first condition of the lemma, we obtain |L(e)| ≥ d(v)

+ 1 4 ∆ + ǫ ∆ -3 ∆ 1/2 ≥ * 1 + 1 2 ǫ 5 4 d(v). So, for each vertex v ∈ B we get e∈E(v) x e ≤ 4 5 d(v) |E(v)| + 1 5 d(v) |{ e = vw | w ∈ S }|;
while for each vertex v in S we can write

e∈E(v) x e ≤ 1 d(v) |E(v)| - 1 5 d(v) |{ e = vw | w ∈ B }|.
We estimate, using that the vertices in S have smaller degree than the vertices in B,

2 e∈E(F ) x e ≤ v∈X e∈E(v) x e ≤ v∈B 4 5 d(v) |E(v)| + v∈S 1 d(v) |E(v)| + e∈E(F ) e=vw, v∈B, w∈S 1 5 d(v) - 1 5 d(w) ≤ v∈B 4 5 d(v) |E(v)| + v∈S 1 d(v) |E(v)| ≤ 4 5 |B| + |S| - 4 5 e(X, V \ X) 1 ∆ .
Now, applying the second condition of the lemma and the presumption for this Case 1, we see that

e(X, V \ X) ≥ 1 4 ∆ |S| + 1 8 ∆ - ǫ |X| ∆ 10 .
Combining the two estimates, we thus obtain

2 e∈E(F ) x e ≤ |X| 4 5 + 2 ǫ 25 - 1 10
.

For ǫ ≤ 1/4 and |X| ≥ 5, the right hand side is at most |X| -1, which shows that such X satisfy the second inequality in the Characterisation of the Matching Polytope.

Case 2 : Every vertex in B has degree at least 7 8 ∆ and every vertex in S has degree at least 5 8 ∆. Applying the first condition of the lemma as in Case 1, we see that for an edge e with endvertices v, w, we have x e ≤ 4 5 |X| ≤ |X| -1, as required.

|L(e)| ≥ d(v) + 1 8 ∆ + ǫ ∆ -3 ∆ 1/2 ≥ * 1 + 1 2 ǫ 9 8 d(v), and if w ∈ B, then we get |L(e)| ≥ d(v) + 3 8 ∆ + ǫ ∆ -3 ∆ 1/2 ≥ * 1 +

Kahn's Algorithm

In this subsection we assume we are given a multigraph H with lists L(e) for each edge e. For any colour γ, H γ is the subgraph of H induced by the edges that contain γ in their list. For the sake of simplicity, we do not distinguish between a subgraph J of H and the graph obtained from J by removing its isolated vertices ( since we are interested in colouring edges, isolated vertices are irrelevant ).

Kahn presents an algorithm in [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF] which shows that the list chromatic index of a multigraph exceeds its fractional chromatic index by o(∆). Actually, the algorithm implicitly contains a subroutine which does more than this, providing a proof of the following result.

Theorem 5.10 ( Kahn [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF] ) For every δ, 0 < δ < 1, and C > 0 there exists a ∆ δ,C such that the following holds for all ∆ ≥ ∆ δ,C . Let H be a multigraph with maximum degree at most ∆, and with a list L(e) of acceptable colours for each edge e. Define the graphs H γ as above.

Suppose that for each colour γ there exists a hard-core distribution p γ on the matchings of H γ , with corresponding marginal x pγ on the edges, satisfying the following conditions :

1.

For every edge e :

γ∈L(e)

x pγ (e) = 1.

2.

For every colour γ : the marginal x pγ is in (1 -δ)MP(H).

3.

For every edge e and colour γ :

x pγ (e) ≤ C ∆ .
Then we can find a proper colouring on the edges of H, using colours from L(e) for each edge e.

Notice that if a hard-core distribution satisfies the hypotheses in the theorem above, then applying Lemma 5.8 and setting K = β C using the β in that lemma, we obtain that the hard-core distributions also satisfy :

4.

For every edge e and colour γ :

λ pγ (e) ≤ K ∆ .
At the heart of Kahn's analysis is the following lemma, Lemma 3.1 in [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF].

RR n➦ 6586

Lemma 5.11 ( Kahn [15] ) For every K, δ > 0, there exist ξ = ξ δ,K , 0 < ξ ≤ δ, and ∆ δ,K such that the following holds for all ∆ ≥ ∆ δ,K . Let H be a multigraph with maximum degree at most ∆, and with a list L(e) of acceptable colours for each edge e. Define the graphs H γ as before. Suppose that for each colour γ we are given a hard-core distribution p γ on the matchings of H γ with activities λ pγ = λ γ and marginals x pγ = x γ , satisfying :

1.

For every edge e :

γ∈L(e)

x γ (e) > e -ξ .

2.

For every colour γ and edge e : λ γ (e) ≤ K ∆ .

Then for all γ there exist matchings M γ in H γ , so that if we set

H ′ = H -γ * M γ * , H ′ γ = H γ - V (M γ ) -γ * M γ * ,
we form lists L ′ (e) be removing no longer allowed colours from L(e), and we let x ′ γ be the marginals corresponding to the activities λ γ on H ′ γ , we have : • For every edge e of H ′ :

γ∈L ′ (e)
x ′ γ (e) > e -δ .

• The maximum degree of H ′ is at most

1 + δ 1 + ξ e -1 ∆.
( The expression (1 + δ)/(1 + ξ) is only there to make further analysis somewhat easier; removing it would give a completely equivalent statement. )

The proof of the lemma utilises the Local Lemma to show that selecting matchings according to the hard-core distribution will, with positive probability, give the required matchings. This proof forms the bulk of Kahn's paper. Once it is proved, Theorem 5.10 follows fairly easily ( although it requires some careful selection of the constants involved ), using the following iterative "construction".

Given a multigraph with lists of acceptable colours and distributions satisfying the hypotheses in the theorem, start with setting H 0 = H, and H 0 γ = H γ for all γ. Once we have obtained H i-1 and H i-1 γ , in iteration i we do the following.

I.

For each colour γ, choose the matching M i γ in H i-1 γ according to the lemma.

II.

If an edge e is in one or more M i γ 's, then assign it a colour chosen uniformly at random from the matchings containing that edge. III. Form H i by removing from H i-1 all edges that have been assigned a colour during this stage.

Form H i γ by removing from H i-1 γ all edges that have been assigned some colour γ * at this stage, and all vertices that are incident to an edge that got assigned colour γ this stage.

The procedure is repeated until for each γ we have obtained matchings N γ = i M i γ , whose removal from H leaves a subgraph U of uncoloured edges such that U has maximum degree at most ∆ 2 e K , whereas for each edge e of U there are at least ∆ e K colours in L(e) which have not been used on any edges incident to e. At this point he finishes the colouring greedily. This proof is given in Section 3 of Kahn's paper, and is fairly easy to extract from what he has actually written there. The bulk of his paper involves guaranteeing the performance desired in each iteration. This done by applying Lemma 3.1 in his paper [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF]. As the reader can check from the lemma as given above, it assumes precisely the hypotheses in the theorem above, so can also be applied in our situation. Kahn deduces his main result from this lemma in Section 3 of his paper. To do so, he first deduces that he can find probability distributions that satisfy the conditions in Theorem 5.10 ( this is done between equations [START_REF] Kohl | List version of L(d, s)-labelings[END_REF] and the unlabelled equation between ( 21) and ( 22) ), and then proves that given distributions satisfying these conditions the result can be proved using the iterative approach INRIA described above. So to extend his result we simply need to drop the part of the proof where he derives our hypotheses from his.

A few more remarks about Kahn's proof are in order. The iterative construction requires O(1) iterations. The bad events which he avoids by applying the Local Lemma are defined in the middle of page 136 of his article [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF]. There are two kinds : an event T v such that its non-occurrence guarantees the degree of a vertex v drops sufficiently, and an event T e such that its non-occurrence ensures that the marginals at an edge e of the hard-core distribution for the next iteration sum to a number close to 1. He defines a distance t > 1 which is a function of δ and K ( and independent of ∆ ) and shows that the probability that a bad event occurs given all the edges of every matching at distance at least t in H from the vertex or edge indexing it is at most p for some p which is ∆ -ω (1) . ( A few remarks : Kahn uses D where we use ∆, and ∆ 1 + ∆ 2 where we use t. The result we have just stated is Lemma 6.3 on page 137. The ω(1) here is with respect to ∆. ) He can then apply the Local Lemma, where the set S Tz ( z a vertex or an edge ) is the set of events indexed by an edge or vertex within distance 2 t of z ( this is also done on pages 136-137 ). The key point is that this set has size at most d = 2 (∆ + 1) ∆ 2t , so we have e p d = o(1).

Modifying the Algorithm

We will adopt Kahn's approach to prove Lemma 5.1. We use his iterative algorithm to colour most of the graph. We simply impose an extra condition that very few edges incident to any vertex of H are involved in conflicts because of their neighbours in J 1 or J 2 . Then, in the final phase, we recolour these edges as well as colouring the uncoloured edges. Our bound on the number of such edges incident to each vertex will ensure that we can do this greedily, even when we take into account colours which cannot be used because of coloured neighbours in J 1 or J 2 . Forthwith the details.

We use the strengthening of Theorem 5.10, obtained by : (i) adding at the end of the first paragraph of that theorem : Suppose further that J 1 is a graph of maximum degree ∆ 1/4 on L(e) and J 2 is a graph of maximum degree ∆ 1/2 on L(e),

(ii) and adding at the end of the last sentence of the theorem : So that no edge of J 2 is monochromatic, and the colours assigned to the endpoints of an edge of j 1 differ by at least ∆ 1/4 .

We call this strengthening Theorem 5.10 * . We first show that it implies Lemma 5.1 and then discuss its proof.

Without loss of generality we will assume that ǫ < 1/200. We set δ = 1 -1 + 1 2 ǫ -1 and C = 3.

We insist that ∆ ǫ exceeds the ∆ δ,C of Theorem 5.10 * . We also assume ∆ ǫ is large enough that certain implicit inequalities used below to bound o(1) terms using ǫ hold. For each edge e and each colour γ in L(e) we set x γ (e) = |L(e)| -1 . Thus, for each edge e we have that γ x γ (e) = 1. Also, we know that for each edge e with endvertices v and w, applying the second condition of Lemma 5.1 with X = {v} and X = {w}, we have that d(v) + d(w) ≥ 1 -1 5 ǫ ∆. Hence applying the first condition of the lemma, we have that |L(e)| ≥ 1 2 -2 5 ǫ ∆ ≥ 1 3 ∆. Thus all of our marginals are at most C ∆ . Applying Lemma 5.9

we see that each of these marginal vectors is in (1 -δ) MP(H) and hence in (1 -δ)MP(H γ ). We can now apply Theorem 5.10 * to obtain a list colouring of the edges of H. We now turn to the proof of Theorem 5.10 * . We let K = β C, using the β from Lemma 5.8 as in the last section, so each activity is bounded by K ∆ . We let H ′ be the graph obtained from H by adding an edge between two vertices if they are endvertices of two edges which are joined in J 1 or J 2 . We note that H ′ has maximum degree less than ∆ 2 .

To resolve a conflict because of J 1 or J 2 , we recolour the conflicting edge which was coloured last, recolouring both edges if they were coloured in the same iteration. Unfortunately, Kahn's algorithm may multi-colour an edge. To deal with this we say that an edge is coloured with the first colour assigned to it. If it is assigned more than one colour in the iteration in which it receives a colour, we colour it with the choice which is smallest.

In each iteration, for each vertex v of H, we let X v be the number of edges e of H incident to v which are coloured with a colour, which is used to colour a neighbour of e in J 1 or is within ∆ 1/4 of a neighbour of e in J 2 . For technical reasons, in this definition if the neighbour f in J 1 or J 2 was uncoloured at the beginning of this iteration we consider conflicts involving all the colours γ such that M γ contains f . We let F (e) be the colours forbidden on e, either because they were assigned to a J 2 neighbour in a previous iteration, or because they are too close to a colour assigned to a J 1 neighbour in a previous iteration.

We will use the variant of Lemma 5.11 in which we add :

(i) at the beginning of its first paragraph : Suppose further that we have a list F (e) of at most ∆ 2/3 colours for each edge e, and graphs J 1 and J 2 , where J 1 has degree at most ∆ 1/3 and J 2 has degree at most ∆ 2/3 , (ii) at the very end a new bullet point item :

• for every vertex v, X v has at most ∆ 4/5 elements.

We call this variant Lemma 5.11 * , and use it to obtain Theorem 5.10 * To prove the lemma, we follow closely the proof of Lemma 5.11 in [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF]. We introduce for each vertex v of H, a new event S v that X v exceeds ∆ 4/5 . In each iteration, along with insisting that all the T e and T v fail, we also insist that all the S v fail. In doing so we use the following claim.

Claim 5.12

The conditional probability that S v holds, given that for every γ we have conditioned on M γ -v-N H ′ (v) = L γ for some matching L γ , is ∆ -ω (1) .

Given the claim, to prove our variant of the lemma, we can use the Local Lemma, just as Kahn did. Because just as with the other events, we have a ∆ -ω (1) bound on the probability that any S v fails given the choice of all the matching edges at distance at least t from the neighbours of v in H ′ ( by applying our claim to all the choices of L γ which extend this choice ). We can therefore apply the Local Lemma iteratively as in the last section. Note here that the set S Tz for an event with index z ∈ V (H) ∪ E(H) will consist of all of those events the index of which is within distance 2 t of z in H ′ rather than H. ( This gives a bound of ∆ 4t for d rather than ∆ 2t but this is still much less than p -1 . ) Thus, we can indeed prove Lemma 5.11 * .

To prove Theorem 5.10 * , we apply Lemma 5.11 * , mimicking Kahn's proof of Theorem 5.10. We eventually obtain a colouring of E(H) -U for some subgraph U of H with maximum degree ∆ 2 e K , such that for each edge e there are at least ∆ e K colours on L(e) which appear on no edge incident to e.

We extend U to U ′ by uncolouring every edge e which is involved in a J 1 or J 2 conflict with an edge f coloured before or at the same time as e. Because we perform O(1) iterations and all the S v hold, we know that U ′ has maximum degree ∆ 2 e K + O(∆ 4/5 ). If we choose ∆ ǫ large enough, then this is less than ∆ e K -3 ∆ 1/2 -1. Hence we can extend our edge-colouring to an edge-colouring of H by colouring the edges of U ′ greedily, whilst at the same time avoiding conflicts due to J 1 or J 2 . This completes the proof of Theorem 5.10 * modulo the claim.

INRIA

Proof of Claim 5.12 To prove our claim we first bound the conditional expected value of X v . We consider each edge e incident to v separately. We show that the conditional probability that e is in a conflict is O(∆ -1/2 ). Summing up over all e incident to v yields that the expected value of X v is O(∆ 1/2 ). We prove this bound for the conflicts involving edges coloured in a previous iteration and edges coloured in this iteration separately.

To begin we consider the previously coloured edges. We actually show that for any edge e, the conditional probability that e is involved in a conflict with a previously coloured edge given for each colour γ a matching N γ such that M γ is either N γ or N γ + e, is O(∆ -1/2 ). Summing up over all the choices for the N γ which extend the L γ , then yields the desired result. If N γ contains an edge incident to e, then M γ = N γ . Otherwise, by the definition of a hard-core distribution :

Pr(M γ = N γ + e) = λ γ (e) 1 + λ γ (e) ≤ λ γ (e) ≤ K ∆ .
The conditional probability we want to bound is the sum over all colours γ of the conditional probability that e is coloured γ and involved in a conflict with a previously coloured J 1 or J 2 neighbour. There are at most ∆(J 1 ) + 2 ∆ 1/4 ∆(J 2 ) colours for which this probability is not zero. For each of these colours, the conditional probability that a conflict actually occurs is at most the conditional probability that e is in M γ . Since this is O(∆ -1 ), the desired bound follows.

We next consider conflicts with edges coloured in this iteration. It is enough to show that the conditional probability that e conflicts with any particular uncoloured J 1 neighbour is O(∆ -1 ) and the probability that it conflicts with a J 2 neighbour is O(∆ -3/4 ). We actually show that for any edge f joined to e by an edge of J 1 ∪ J 2 , the conditional probability that e is involved in a conflict with f , given for each colour γ a matching N γ such that M γ is one of :

N γ , N γ + e, N γ + f , N γ + e + f , is O(∆ -1 ) if f is in J 1 , and O(∆ -3/4 ) if f is in J 2 .
Summing up over all the choices for the N γ which extend the L γ , then yields the desired result. Suppose first that f is adjacent to e in J 1 . We obtain our bound on the probability that e and f get the same colour by summing the probability they both get a specific colour γ over all the at most 3 2 + ǫ ∆ colours on L(e). For each such colour, as in the last paragraph, we obtain that given the conditioning

Pr(M γ = N γ + e + f ) ≤ λ γ (e) λ γ (f ) ≤ K ∆ 2 .
Summing over our choices for γ yields the desired result. If f is adjacent to e in J 2 , then having picked a choice for γ we have at most 2 ∆ 1/4 choices for a colour γ ′ on f that cause a conflict. Proceeding as above, we can show that the conditional probability that e is coloured γ and f is coloured γ ′ is at most K ∆

2

. This yields the desired result.

We next bound the probability that X v exceeds ∆ 4/5 by showing that it is concentrated. We note that if we change the choice of one M γ , leaving all the other random matchings unchanged, then the only new J 1 or J 2 conflicts counted by X v involve edges coloured with a colour within ∆ 1/4 of γ. There are at most 2 ∆ 1/4 + 1 such edges incident to v. Thus, such a change can change X v by at most 2 ∆ 1/4 + 1. Furthermore, each conflict involves at most two of the matchings ( only one if it also involves a previously coloured vertex ). So, to certify that there were at least s conflicts involving edges incident to v in an iteration we need only produce at most 2 s matchings involved in these conflicts. It follows by a result of Talagrand [START_REF] Talagrand | Concentration of measure and isoperimetric inequalities in product spaces[END_REF] ( see also [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]Chapter 10] ) that the probability that X v exceeds its median M by more than t is at most exp -Ω t 2 ∆ 1/2 M = exp -Ω t 2 ∆ 1/2 . Since the median of X v is at most twice its expectation, setting t = 1 2 ∆ 4/5 yields the desired result. This completes the proof of the claim, and hence of Lemma 5.11 * , Theorem 5.10 * and Lemma 5.1.

The Final Stage : Deriving Lemma 3.2

With Lemma 5.1 in hand, it is an easy matter to prove Lemma 3.2. In doing so we consider the natural bijection between the core R of H * and E(H), referring to these objects using whichever terminology is convenient. We sometimes use both names for the same object in the same sentence.

Before we really start, one observation concerning degrees. For a vertex v in H, the condition in Lemma

3.2, taking X = {v}, gives d G-R (v) -d H (v) ≤ 1 10 ǫ ∆. Since d G-R (v) = d G (v) -d H (v), this means that d H (v) ≥ 1 2 d G (v) -1 20 ǫ ∆, and hence d G (v) -d H (v) ≤ 1 2 d G (v) + 1 20 ǫ ∆ ≤ 1 2 + 1 20 ǫ ∆.
This will guarantee that all the lists of colours we will consider below are not empty.

Next, for two vertices x, y from R, if x and y are adjacent in G, we add the edge xy to J 2 , and if x and y are adjacent in G 2 , but do not correspond to adjacent edges in H, then we add the edge xy to J 1 . Since vertices in R have degree at most ∆ 1/4 in G, we get the required bounds on the degree for vertices in J 1 and J 2 in Lemma 5.1. Now first suppose that every vertex v in H has degree ∆ in G. For an edge e = vw in H, set L ′ (e) to be a subset of 3 2 +ǫ ∆-(∆-d H (v))-(∆-d H (w))-3 ∆ 1/2 colours in L(e) which appear on no vertex of V -R which is a neighbour of e in G 2 and are not within ∆ 1/4 of any colour appearing on a neighbour of e in G. This is possible because in G 2 , e is adjacent to at most (∆ -d H (v)) + (∆ -d H (w)) neighbours of v and w in V -R, and at most ∆ 1/2 other vertices of V -R ( since the vertex in G representing the edge e is removable, hence has at most ∆ 1/4 neighbours non-adjacent to v and all these vertices have degree at most ∆ 1/4 ). Finally, the condition in Lemma 5.1 on the edges leaving an odd set X of vertices of H holds because of the corresponding condition for all sets X in the statement of Lemma 3.2. So applying Lemma 5.1, we are done in this case.

In general this approach does not work because for a vertex v of H of degree less than ∆, we do not have that ∆ -d H (v) is equal to the number of edges from v to V -R, so our two conditions are not quite equivalent. In order to fix this, we use a simple trick. Form G by taking two disjoint copies G (1) and G (2) of G, with corresponding copies H (i) , R (i) , J (i) 1 , J (i) 2 , i = 1, 2, and copy all the lists of colours on the vertices. For each vertex v of H, we add ∆ -d G (v) subdivided edges between its two copies v (1) and v (2) . Give an arbitrary list of 3 2 + ǫ ∆ colours to the vertices at the middle of these new subdivided edges. Let H be the multigraph formed from combining H (1) and H (2) with the new multiple edges between copies of vertices of H. Similarly, take R the union of R (1) , R (2) and all vertices in the middle of the new edges, and set J j = J

(1) j ∪ J

(2) j , j = 1, 2. Note that the degrees in J 1 and J 2 haven't changed, so we can still use them in Lemma 5.1.

Recall that for i ∈ {1, 2} and all v ∈ H (i) , we have ∆ -d H (v) = d G (v) -d H (i) (v). Now we choose lists of colours on the edges of H. Each new edge v (1) v (2) gets an arbitrary list of 3 2 + ǫ ∆ -(∆d H (v (1) ))-(∆-d H (v (2) ))-3 ∆ 1/2 = 3 2 +ǫ ∆-2 (d G (v)-d H (v))-3 ∆ 1/2 colours from the 3 2 +ǫ ∆ colours we gave on the vertex in the middle of it. On the two copies of an edge e = vw of H we take the same list of We note that if we can find a proper colouring of L(H) using the chosen lists which avoids conflicts, then we get two colourings of G 2 -R that can be extended to R. We apply Lemma 5.1 to prove that we can indeed find such an acceptable colouring. To do so, we only need to show that for every odd set X of vertices of H, we have v∈X (∆ -d H (v)) -e(X, V (H) \ X) ≤ ǫ |X| ∆ 10 .

INRIA

In fact, we will do this for all subsets X of V (H). We set X (i) = X ∩ V (H (i) ), i = 1, 2. We immediately get that e(X, V (H) \ X) ≥ e(X (1) , V (H (1) ) \ X (1) ) + e(X (2) , V (H (2) ) \ X (2) ) ( since on the right hand right we are ignoring the edges between the two copies of H ). Recall that ∆ -d H (v) = d G-H (v) for a v in H. Using the condition in Lemma 3.2 for the two copies of H, this gives v∈X (∆ -d H (v)) -e(X, V (H) \ X) ≤ v∈X (1) d G-H (v) + v∈X (2) d G-H (v)

-e(X (1) , V (H (1) ) \ X (1) ) -e(X (2) , V (H (2) ) \ X (2) )

≤ ǫ |X (1) | ∆ 10 + ǫ |X (2) | ∆ 10 = ǫ |X| ∆ 10 .
and we are done.

Conclusions and Discussion

In this paper, we showed that the chromatic number of the square of a graph G of a fixed nice family, χ(G 2 ), is at most 3 2 +o(1) ∆(G). Planar graphs form a nice family of graphs. In fact, we can characterise nice families of graphs in Theorem 2.4. But many questions remain.

One can prove a bound of constant times the maximum degree for the chromatic number of the square of graphs from a minor-closed family. Krumke, Marathe and Ravi [START_REF] Krumke | Approximation algorithms for channel assignment in radio networks[END_REF] showed that if a graph G is q-degenerate ( there exists an ordering v 1 , v 2 , . . . , v n of the vertices such that every v i has at most q neighbours in {v 1 , . . . , v i-1 } ), then its square is ((2 q -1) ∆(G))-degenerate -the same ordering does the job. But for every minor-closed family F, there is a constant C F such that every graph in F is C F -degenerate ( see Theorem 2.2 and the first paragraph of Section 4 ). Hence G 2 is ((2 C F -1) ∆(G))degenerate for every G ∈ F and so its list chromatic number is at most (2 C F -1) ∆(G) + 1.

But it unlikely that this is the best possible bound. Question 6.1 For a given minor-closed family F graphs ( with F not the set of all graphs ), what is the smallest constant D F so that χ(G 2 ) ≤ (D F + o(1)) ∆(G) for all G ∈ F ?

The following examples show that for F the class of K 4,4 -minor free graphs we must have D F ≥ 2. Let V 1 , . . . , V 4 be four disjoint sets of m vertices, and let X = {x 12 , x 13 , x 14 , x 23 , x 24 , x 34 } be a further six vertices. Let G m be the graph with vertex set It is easy to generalise these examples to show that for F the class of K k,k -minor free graphs, k ≥ 3, we must have D F ≥ 1 2 k. But even for nice classes of graphs, many open problems remain. Our proof on the bound of the ( list ) chromatic number does not provide an efficient algorithm. So, for a nice family F, it would be interesting to find an efficient algorithm to find a colouring of a graph G ∈ F with at most 3 2 +o(1) ∆(G) colours.

X ∪ V 1 ∪ • • • ∪ V 4 ,
Moreover, our result suggests that Wegner's Conjecture should be generalised to nice families of graphs and to list colouring.

3 2 ∆Figure 1 :

 21 Figure 1: The planar graphs G k .

e∋v x e < 1 , and 2 .

 12 for all F ⊆ H with |V (F )| ≥ 3 odd : e∈E(F ) x e < 1 2 (|V (F )| -1).

3 2 +

 2 ǫ ∆ -(∆ -d H (v)) -(∆ -d H (w)) -3 ∆ 1/2 colours. Since this is equal to

3 2 +

 2 ǫ ∆ -(d G (v) -d H (v)) -(d G (w) -d H (w)) -3 ∆ 1/2 ,we can still choose this list to be distinct from the colours used on the neighbours of this edge in G 2 -R.

  and edges between any x ij and all vertices inV i ∪ V j , 1 ≤ i < j ≤ 4. It is easy to check that G m is K 4,4 -minor free. For m ≥ 2 we have ∆(G m ) = d Gm (x ij ) = 2 m. Moreover, all vertices in V 1 ∪ • • • ∪ V 4 are adjacent in G 2 m , and hence χ(G 2 m ) ≥ 4 m = 2 ∆(G m ).

  Proposition 2.1 Let B be a non-empty set of vertices of the planar graph G, and let A be the collection of vertices in V \ B which have at least three neighbours in B. Then we have e(A, B) < 6 |B|. Proof Consider the bipartite graph H with parts A and B, and the edges of G between the parts. Then e(A, B) = |E(H)| ≥ 3 |A|. But since H is planar and bipartite, it has average degree less than 4.Proof First suppose that F is nice, with constant β F from the definition of nice. And suppose there is a graph G ∈ F with K 3,k as a minor for some k. Since F is minor-closed, this means K 3,k itself is a graph in F. By taking B the set of three vertices in K 3,k from one part of the bipartition, and A the remaining k vertices, we see that we must have 3 k = e(A, B) ≤ β F |B| = 3 β F . It follows that every graph in

	Hence we have	4 >	2 |E(H)| |A| + |B|	≥	6 |A| |A| + |B|	.
	From the outer inequality, 6 |A| < 4 (|A| + |B|) and so |A| < 2 |B|; and now from the left inequality
	|E(H)| < 2 (|A| + |B|) < 6 |B|.
	A similar proof shows that graphs embeddable on a given surface form a nice family.
	Theorem 2.2 ( Mader [26] )
	For any graph H, there is an constant C H such that every H-minor free graph has average degree at
	most C H .
	In the proof of Theorem 2.2, Mader showed that C H ≤ c |V (H)| log |V (H)|, for some constant c.
	This upper bound was later lowered independently by Kostochka [19] and Thomason [33] to C H ≤
	c ′ |V (H)| log |V (H)|, for some constant c ′ .
	Corollary 2.3 Any H-minor free graph with n vertices has at most	C H 2	n triangles.
	Proof We prove the result by induction on n, the result holding trivially if n ≤ 3. Let G be a H-minor
	free graph with n vertices. By Theorem 2.2, its average degree is at most C H . So G has a vertex v of degree at most C H . The vertex v is in at most C H triangles. Now by induction, G -v has at most 2 C H 2 (n -1) triangles. Hence G has at most C H 2 n triangles.
	For an extension of this result see Lemma 2.1 of Norine et al. [30].
	Theorem 2.4
	A class of graphs is nice if and only if it is minor-closed and does not contain K 3,k for some k.

RR n➦ 6586

To avoid confusion between an edge "e" and the base of the natural logarithms

2.718. . . , we will use the roman letter "e" for the latter one.RR n➦ 6586

Part of the research for this paper was done during a visit of FH, JvdH and BR to the Department of Applied Mathematics ( KAM ) at the Charles University of Prague; during a visit of FH, CMcD and BR to Pacific Institute of Mathematics Station in Banff ( while attending a focused research group program ); and during a visit of JvdH to Projet Mascotte, INRIA in Sophia-Antipolis ( funded by Hubert Curien programme Alliance 15130TD and the British Council Alliance programme ). The authors would like to thank all institutes involved for their hospitality. This research is also partially supported by the European project FET AEOLUS.

Conjecture 6.2

Let F be a nice family of graphs. Then for any graph G ∈ F with ∆(G) sufficiently large, χ(G 2 ) ≤ ch(G 2 ) ≤ 3 2 ∆(G) + 1

The results of Lih, Wang and Zhu [START_REF] Lih | Coloring the square of a K 4 -minor free graph[END_REF] and Hetherington and Woodall [START_REF] Hetherington | List-colouring the square of a K 4 -minor-free graph[END_REF] show that the conjecture is true when F is the family of K 4 -minor free graphs.

As ω(G 2 ) ≤ χ(G 2 ), our result implies ω(G 2 ) ≤ 3 2 + o(1) ∆(G). But does there exist a simple proof showing this inequality ? Furthermore, another step towards Wegner's Conjecture would be to prove that ω(G 2 ) ≤ 3 2 ∆(G) + 1 for all planar graphs G with ∆(G) ≥ 8. Note that this last inequality is tight as shown by the examples of Figure 1. More generally, can we prove that ω(G 2 ) ≤ 3 2 ∆(G) + 1 for all graphs G in a nice family F with ∆(G) large enough ?

A major part of the proof of our result is a reduction to list edge-colouring of line graphs. For edge-colourings, Kahn [START_REF] Kahn | Asymptotics of the list-chromatic index for multigraphs[END_REF] proved that asymptotically the list chromatic number equals the fractional chromatic number. This may suggest that the same could be true for squares of planar graphs, or more generally for squares of graph of a nice family.

Problem 6.3

Let G be a graph of a fixed nice family F.

Finally, the already mentioned conjecture of Kostochka and Woodall [START_REF] Kostochka | Choosability conjectures and multicircuits[END_REF] that for every graph G we have ch(G 2 ) = χ(G 2 ), is an intriguing problem. This problems mimics the well-known list colouring conjecture that the list edge-chromatic number of a multigraph is equal to its edge-chromatic number ( see Jensen and Toft [START_REF] Jensen | Graph Coloring Problems[END_REF]Section 12.20] ). These two conjectures indicate an even deeper relation between colouring the square of graphs and edge-colouring multigraphs than what we have been able to prove so far.

INRIA