Hervé Hocquard

Mickaël Montassier

André Raspaud

Petru Valicov

On strong edge-colouring of subcubic graphs

Keywords: Strong edge-colouring, subcubic graphs, planar graphs, maximum average degree

A strong edge-colouring of a graph G is a proper edge-colouring such that every path of length 3 uses three different colours. In this paper we improve some previous results on the strong edgecolouring of subcubic graphs by showing that every subcubic graph with maximum average degree strictly less than 7 3 (resp. 5 2 , 8 3 , 20 7 ) can be strongly edge-coloured with six (resp. seven, eight, nine) colours. These upper bounds are optimal except the one of 8 3 . Also, we prove that every subcubic planar graph without 4-cycles and 5-cycles can be strongly edge-coloured with nine colours.

Introduction

In this paper the graphs considered are finite, simple and without loops. A proper edge-colouring of a graph G = (V, E) is an assignment of colours to the edges of the graph such that two adjacent edges do not use the same colour. A strong edge-colouring (called also distance 2 edge-colouring) of a graph G is a proper edge-colouring of G, such that the edges of any path of length 3 use three different colours. We denote by χ ′ s (G) the strong chromatic index of G which is the smallest integer k such that G can be strongly edge-coloured with k colours.

Strong edge-colouring was introduced by Fouquet and Jolivet in 1983 [START_REF] Fouquet | Strong edge-colorings of graphs and applications to multi-k-gons[END_REF][START_REF] Fouquet | Strong edge-coloring of cubic planar graphs[END_REF]. Strong edgecolouring can be used to model the conflict-free channel assignment in radio networks [START_REF] Barrett | Strong edge coloring for channel assignment in wireless radio networks[END_REF][START_REF] Nandagopal | Achieving MAC layer fairness in wireless packet networks[END_REF][START_REF] Ramanathan | A unified framework and algorithm for (T/F/C) DMA channel assignment in wireless networks[END_REF][START_REF] Ramanathan | Scheduling algorithms for multi-hop radio-networks[END_REF].

Let ∆(G) be the maximum degree of a graph G (we will use ∆ if no ambiguity). The following conjecture was posed by Erdős and Nešetřil [START_REF] Erdős | Problems and results in combinatorial analysis and graph theory[END_REF][START_REF] Erdős | Problem[END_REF] and revised by Faudree et al. [START_REF] Faudree | The strong chromatic index of graphs[END_REF] and Chung et al. [START_REF] Chung | The maximum number of edges in 2K 2 -free graphs of bounded degree[END_REF]:

Conjecture 1 (Erdős and Nešetřil [START_REF] Erdős | Problems and results in combinatorial analysis and graph theory[END_REF][START_REF] Erdős | Problem[END_REF]). For every graph G,

χ ′ s (G) ≤ 5 4 ∆ 2 , if ∆ is even; 1 4 (5∆ 2 -2∆ + 1), if ∆ is odd.
If this conjecture is true, then the given upper bounds for the strong chromatic index are tight as the authors gave constructions of graphs with strong chromatic index reaching these bounds. The conjecture was verified for graphs having ∆ ≤ 3 [START_REF] Andersen | The strong chromatic index of a cubic graph is at most 10[END_REF][START_REF] Horák | Induced matchings in cubic graphs[END_REF]. When ∆ > 3, the only case on which some progress was made is when ∆ = 4 and the best upper bound stated is χ ′ s (G) ≤ 22 [START_REF] Cranston | Strong edge-coloring of graphs with maximum degree 4 using 22 colors[END_REF]. An upper bound for the strong chromatic index of subcubic graphs in terms of the maximum average degree mad(G) = max 2|E(H)|

|V (H)| , H ⊆ G , was given in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF]. More precisely, it was proved the following.

Theorem 1 (Hocquard and Valicov [11]). Let G be a subcubic graph (a graph with ∆ ≤ 3).

1. If mad(G) < 15 7 , then χ ′ s (G) ≤ 6.

2. If mad(G) < 27 11 , then χ ′ s (G) ≤ 7.

3. If mad(G) < 13 5 , then χ ′ s (G) ≤ 8.

4.

If mad(G) < 36 13 , then χ ′ s (G) ≤ 9.

Recall that the girth of a graph is the length of a shortest cycle in this graph. As every planar graph with girth g satisfies mad(G) < 2g g-2 , the following corollary, can be easily derived from Theorem 1:

Corollary 1 (Hocquard and Valicov [11]). Let G be a planar subcubic graph with girth g.

1. If g ≥ 30, then χ ′ s (G) ≤ 6.

2. If g ≥ 11, then χ ′ s (G) ≤ 7.

3. If g ≥ 9, then χ ′ s (G) ≤ 8.

4. If g ≥ 8, then χ ′ s (G) ≤ 9.

In this paper, we strengthen Theorem 1 by proving that:

Theorem 2. Let G be a subcubic graph.

1. If mad(G) < 7 3 , then χ ′ s (G) ≤ 6.

2. If mad(G) < 5 2 , then χ ′ s (G) ≤ 7.

3. If mad(G) < 8 3 , then χ ′ s (G) ≤ 8.

4.

If mad(G) < 20 7 , then χ ′ s (G) ≤ 9.

For cases 1, 2 and 4, the given upper bounds on the maximum average degree are sharp: there exist graphs with mad(G) = 7 3 (resp. 5 2 , 20 7 ) which are not strong edge-colourable with six (resp. 7, 9) colours. Examples of such graphs are given in Section 2.2.

For planar graphs it follows:

Corollary 2. Let G be a planar subcubic graph with girth g:

1. If g ≥ 14, then χ ′ s (G) ≤ 6. 2. If g ≥ 10, then χ ′ s (G) ≤ 7.

3. If g ≥ 8, then χ ′ s (G) ≤ 8. 4. If g ≥ 7, then χ ′ s (G) ≤ 9.
In this paper we are also interested in finding a bound for the strong chromatic index of planar subcubic graphs. The interest for this class of graphs is motivated by the following conjecture:

Conjecture 2 (Faudree et al. [7]). If G is a planar subcubic graph, then χ ′ s (G) ≤ 9.
If the conjecture is true, then it is the best possible bound since the prism P has χ ′ s (P ) = 9 (see Figure 1). An interesting fact about Conjecture 2 is that from the algorithmic aspect the problem of computing the strong chromatic index was proved to be NP-complete for the class of subcubic planar graphs with an arbitrarily large girth [START_REF] Hocquard | Strong edge colouring and induced matchings[END_REF].

For general planar graphs, an upper bound in terms of ∆ was proved by Faudree et al. [START_REF] Faudree | The strong chromatic index of graphs[END_REF]:

Theorem 3 (Faudree et al. [7]). If G is a planar graph, then χ ′ s (G) ≤ 4∆ + 4 for ∆ ≥ 3.
In case of planar graphs we improve the fourth part of Corollary 2 and give a partial answer to Conjecture 2, by showing the following: Theorem 4. Let G be a planar subcubic graph containing neither induced 4-cycles, nor induced 5-cycles. Then χ ′ s (G) ≤ 9.

The paper is organized as follows. In Section 2 we prove Theorem 2 and discuss the optimality of the upper bounds on the maximum average degree. In Section 3 we provide the proof of Thorem 4.

Let us introduce some notations.

Definitions and notations. Two edges are at distance 1 if they share one of their ends and they are at distance 2 if they are not at distance 1 and there exists an edge adjacent to both of them.

Let d G (v) (or d(v) if it is clear from the context) denote the degree of a vertex v in a graph G. A vertex of degree k (resp. at most k) is called a k-vertex (resp. k --vertex ). A 3 k -vertex is a 3-vertex adjacent to exactly k 2-vertices. A bad 2-vertex is a 2-vertex

Bounds using maximum average degree

Proof of Theorem 2

The proof is done by induction. Let H be a minimum counterexample. In each of the cases, first of all we prove the non-existence of some set of subgraphs S in H. In the next step, we use the discharging technique in order to obtain a contradiction. For this, we define a weight function ω : V (H) → R with ω(x) = d(x)m (where m ∈ R is the value of the upper bound on the maximum average degree given by Theorem 2). An important observation is that by hypothesis on the maximum average degree, the total sum of weights must be strictly negative. Next, we define discharging rules to redistribute weights and once the discharging process is finished, a new weight function ω * will be produced. During the discharging process the total sum of weights is kept fixed. Nevertheless, by the non-existence of S, it will follow that ω * (x) ≥ 0 for all x ∈ V (H). This will lead to the following contradiction:

0 ≤ x ∈ V (H) ω * (x) = x ∈ V (H) ω(x) < 0
Therefore, such a counterexample cannot exist.

First part

Let H be a counterexample to Theorem 2.1 minimizing |E(H)| + |V (H)|: H is not strong edge-colourable with six colours, mad(H) < 7 3 and for any edge e, χ ′ s (He) ≤ 6. One can assume that H is connected; otherwise, by minimality of H, we can colour each connected component independently. In this subsection, a 3-vertex adjacent to a 1-vertex is a light 3-vertex. Otherwise it is a heavy 3-vertex.

In order to proof our result we need the following claim proved in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF]:

Claim 1. (Hocquard and Valicov [11]) The minimal counterexample H to Theorem 2.1 satisfies the following properties:

1. H does not contain a 1-vertex adjacent to a 2-vertex.

2.

H does not contain a 3-vertex adjacent to a 1-vertex and a 2-vertex.

3.

H does not contain a 3-vertex adjacent to two 1-vertices. We prove the second item. Suppose H contains a path stuvw where s, t, v and w are four light 3-vertices, u is a 3-vertex adjacent to a light 3-vertex x distinct from s, t, v, w. Call s 1 (resp. t 1 , v 1 , w 1 , x 1 ) the neighbour of s (resp. t, v, w, x) of degree 1. Let r (resp. y, z) be the third neighbour of s (resp. x, w). Also, for i = 1, 2, let r i (resp. y i , z i ) be the neighbours of r (resp. y, z), other than s (resp. x, w). By Claims 1.2 and 1.3, r, y and z are 3-vertices. By Claims 1.5 and 2.1, we can assume that Figure 2 illustrates the given configuration (with r, y, z possibly not distinct).

Let us consider H ′ = H \ {ss 1 , tt 1 , vv 1 , ww 1 , xx 1 , st, tu, uv, vw, ux}. By minimality of H, there exists a strong edge-colouring φ of H ′ , using six colours. We show how to extend this colouring to

H. r r 1 r 2 s s 1 t t 1 u v v 1 w w 1 z z 1 z 2 x x 1 y y 1 y 2 Figure 2: The configuration of Claim 2.2
Without loss of generality we can suppose that φ(xy) = 1, φ(yy 1 ) = 2 and φ(yy 2 ) = 3. First, we colour edge ux and we distinguish two cases:

1. Suppose that rs is not coloured in {1, 2, 3}, say φ(rs) = 4. Colour uv with a colour in {φ(yy 1 ), φ(yy 2 )} that does not appear on wz. Finally, we consider the remaining edges in the following order: vw, ww 1 , vv 1 , tu, st, ss 1 , tt 1 and xx 1 . At each step, there exists an available colour for the corresponding edge. Similarly, we get the result if wz is not coloured in {1, 2, 3}.

2. Suppose now that φ(rs), φ(wz) ∈ {1, 2, 3}. Then it is easy to observe that there exists a colour, say 4, such that ux and ss 1 , can be coloured with 4. We set φ(ux) = φ(ss 1 ) = 4.

Next, we distinguish the following cases for φ(rs) and φ(wz):

• Suppose φ(rs) ∈ {φ(yy 1 ), φ(yy 2 )} = {2, 3} and φ(wz) = φ(rs). Without loss of generality we can suppose that φ(rs) = φ(yy 1 ) = 2. Then we assign φ(uv) = 2. We colour the remaining edges in the following order: vw, ww 1 , vv 1 , tu, st, tt 1 and xx 1 . Note that at each step, there exists a colour left for the corresponding edge.

• Suppose φ(rs) ∈ {φ(yy 1 ), φ(yy 2 )} = {2, 3} and φ(wz) = φ(rs). Without loss of generality we can suppose that φ(wz) = φ(rs) = 2 and we assign φ(uv) = 3. Suppose we can assign φ(ww 1 ) = 4. Next, we colour first st and then tu (note that at each step there is at least one colour left). If there is a colour left for vw, then the colouring of H can be finished easily as edges tt 1 , vv 1 and xx 1 are pairwise at distance 3 and for each of these edges there would be a colour left. Therefore, there is no colour left for vw which implies that {φ(tu), φ(zz 1 ), φ(zz 2 )} = {1, 5, 6} and since tu cannot be coloured 1, without loss of generality we can assume φ(tu) = 5, φ(zz 1 ) = 1 and φ(zz 2 ) = 6. Similarly, by uncolouring st, recolouring tu with 6 and assigning to vw colour 5, we conclude that {φ(rr 1 ), φ(rr 2 )} = {1, 5}. But then we do the following reassignment of colours φ(ss

1 ) = 6, φ(st) = 4, φ(tu) = 5, φ(ux) = 6, φ(vw) = 4, φ(ww 1 ) = 5.
Finally there is a colour left for each of the edges tt 1 , vv 1 and xx 1 , thus we are done. Suppose ww 1 cannot be coloured with 4. Therefore, without loss of generality φ(zz 1 ) = 4. On the other hand, recall that φ(ss 1 ) = φ(ux) = 4 and by previous paragraphs, it is not possible to colour ss 1 , ux and ww 1 with the same colour (4, 5 or 6). Hence we must have {5, 6} ⊆ {φ(zz 2 ), φ(rr 1 ), φ(rr 2 )}. Obviously one of the colours 5 or 6, say 5, is not assigned to zz 2 and is assigned to either rr 1 or rr 2 (we can suppose φ(rr 1 ) = 5). Hence we can assign φ(ww 1 ) = φ(tu) = 5 and we colour the remaining edges in the following order: vw, vv 1 , st, tt 1 , xx 1 . Observe that at each step there exists at least one colour left for every edge.

• Suppose {φ(rs), φ(wz)} ∩ {φ(yy 1 ), φ(yy 2 )} = ∅. Hence, φ(rs) = φ(wz) = 1. We assign φ(tu) = 2 and then we colour the following edges in the given order: st, vw, uv, vv 1 , tt 1 and xx 1 . It remains to colour ww 1 . If we have a colour left for ww 1 , then we are done. Otherwise, {φ(uv), φ(vv 1 ), φ(vw), φ(zz 1 ), φ(zz 2 )} = {2, 3, 4, 5, 6}. Therefore, {φ(uv), φ(vv 1 ), φ(vw)} = {3, 5, 6} and {φ(zz 1 ), φ(zz 2 )} = {2, 4}. But then we permute the colours of tu and uv and we obtain a free colour for ww 1 (which is the same as the colour of tu), a contradiction.

As a corollary from the proof of Claim 2 we derive the following:

Corollary 3. The minimal counterexample H to Theorem 2.1 does not contain a path stuvw where s, t, v and w are either light 3-vertices or 2-vertices and u is a 3-vertex adjacent to a vertex x which is either a light 3-vertex x or a 2-vertex.

Let H ′′ be the graph obtained from H by removing all 1-vertices of H, i.e.

H ′′ = H \ {v ∈ V (H), d H (v) = 1}.
Clearly, H ′′ is connected and mad(H ′′ ) < 7 3 . One can derive the following structural properties of H ′′ : Claim 3. Due to Claim 1 and to Corollary 3, H ′′ has the following properties:

1. δ(H ′′ ) ≥ 2, where δ(H ′′ ) is the minimum degree of H ′′ (from Claim 1.1 and 1.3).

2. H ′′ does not contain a path uvw where u, v, w are 2-vertices (from Claims 1.2, 1.4 and 1.5).

H ′′ does not contain a 3 3 -vertex adjacent to two bad 2-vertices (from Corollary 3).

For each vertex x of H ′′ , we assign a charge w(x) equal to d(x)- 7 3 . We apply now a discharging procedure on H ′′ with the following rules: (R1) Every 3-vertex gives 1 3 to each adjacent bad 2-vertex. (R2) Every 3-vertex gives 1 6 to each adjacent good 2-vertex.

Let v ∈ V (H ′′ ) be a k-vertex. By Claim 3.1, k ≥ 2.
Consider the following cases:

Case k = 2. Observe that ω(v) = -1 3 . Suppose v is a bad 2-vertex. By Claim 3.2, v is adjacent to a 3-vertex. Hence, by (R1), ω * (v) = -1 3 + 1 3 = 0. If v is a good 2-vertex, then ω * (v) = -1 3 + 2 × 1 6 = 0 by (R2). Case k = 3. Observe that ω(v) = 2
3 . Suppose v is adjacent to a bad 2-vertex. By Claim 3.3, v is not adjacent to another bad 2-vertex. Hence, by (R1) and (R2),

ω * (v) ≥ 2 3 -1× 1 3 -2× 1 6 = 0. If v is not adjacent to a bad 2-vertex, then ω * (v) ≥ 2 3 -3 × 1 6 > 0 by (R2).
Therefore, H ′′ cannot exist and consequently H does not exist neither. This completes the proof.

Second part

Let H be a counterexample to Theorem 2. (c) or w 2 is a light 3-vertex.

Proof Claims 4.1 to 4.4 are proved in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF]. We now prove Claim 4.5. Suppose H contains a path uvw where u is a

3 3 -vertex, v is a 2-vertex, w is a 3 2 -vertex and w is adjacent to a 2-vertex w 1 (distinct from v) and to a 3-vertex w 2 . Let H ′ = H \ {u 1 u, u 2 u, uv, vw}.

By minimality of H, χ ′

s (H ′ ) ≤ 7 and there exists a strong edge-colouring φ of H ′ , which uses seven colours. We will extend this colouring to H. We colour the edges vw, uv and u 2 u in this order. Note that at each step there exists at least one colour left for the corresponding edge. In order to complete the strong edge-colouring of H, we must assign a colour to

u 1 u. If | 7 \SC(N 2 (u 1 u))| ≥ 1, then we are done. Hence | 7 \ SC(N 2 (u 1 u))| = 0 and since |N 2 (u 1 u)| = 7
, the edges of N 2 (u 1 u) must be assigned distinct colours. Next, observe that it is possible to colour u 1 u with the colour of u 2 u, uncolour u 2 u and then apply the same argument as previously to show that all the edges of N 2 (u 2 u) must be assigned distinct colours. And then similarly, it is possible to colour u 1 u with the colour of uv, to uncolour uv and if there is no colour left for uv, then all the colours of N 2 (uv) must be distinct. We conclude that w 1 = u 1 , u 2 and w 2 = x, y, x 1 , x 2 , y 1 , y 2 . Hence the configuration and its fixed precolouring of edges is as depicted in Figure 3.

5.a Suppose w 1 is adjacent to a 3 3 -vertex t as in Figure 4.

Let us consider the edge ww 1 . Observe that SC(N 2 (ww 1 )) contains the colours 1, 4 and 5. Otherwise, we can recolour ww 1 with 1 (or 4, or 5), vw with 6 and u 1 u with 3. This extends the colouring to whole H, a contradiction. Observe that 3 ∈ {φ(tt 1 ), φ(tt 2 )}. Otherwise, we can permute the colours of vw and ww 1 , and assign colour 3 to u 1 u. Similarly, observe that 2 ∈ {φ(w 1 t), φ(tt 1 ), φ(tt 2 ), φ(w 2 z 1 ), φ(w 2 z 2 )}. Otherwise, we can permute the colours of ww 1 and uv, and colour u 1 u with 2.

x x 1 x 2 y y 1 y 2 u 1 u 2 u v w w 1 t t 1 t 2 w 2 z 1 z 2 • • • • • •
y 2 u 1 u 2 u v w w 2 w 1 z 1 z 2 t t 1 t ′ 1 t 2 t ′
From the above, we conclude that {φ(w 1 t), φ(tt 1 ), φ(tt 2 ), φ(w 2 z 1 ), φ(w 2 z 2 )} = {1, 2, 3, 4, 5} and 3 ∈ {φ(tt 1 ), φ(tt 2 )} (w 1 t, tt 1 , tt 2 , w 2 z 1 , w 2 z 2 are assigned pairwise distinct colours).

Suppose that {φ(t

1 t ′ 1 ), φ(t 2 t ′ 2 )} = {φ(w 2 z 1 ), φ(w 2 z 2 )}. Let α ∈ {φ(w 2 z 1 ), φ(w 2 z 2 )} \ {φ(t 1 t ′ 1 ), φ(t 2 t ′ 2 )}, α ∈ {1, 2
, 4, 5} (because 3 ∈ {φ(tt 1 ), φ(tt 2 )}). We do the following assignment of colours (in the given order): φ(u 1 u) = 2, φ(uv) = 3, φ(vw) = 6, φ(ww 1 ) = φ(w 1 t), φ(w 1 t) = α.

It follows that {φ(t 1 t ′ 1 ), φ(t 2 t ′ 2 )} = {φ(w 2 z 1 ), φ(w 2 z 2 )} and 6 ∈ {φ(t 1 t ′ 1 ), φ(t 2 t ′ 2 )}. But then we permute the colours of w 1 t and ww 1 , recolour uv with colour 6 and assign to u 1 u colour 2. We obtain a strong edge-colouring of H, a contradiction. 5.b Suppose w 2 is a 3 2 -vertex as depicted in Figure 5. Observe that 3 ∈ {φ(z 1 s), φ(z 2 r)}. Otherwise we can permute the colours of vw and ww 2 , and assign 3 to u 1 u. Observe that 1, 2, 4, 5 ∈ {φ(w 1 t), φ(w 2 z 1 )φ(w 2 z 2 ), φ(z 1 s), φ(z 2 r)}. Otherwise we can recolour ww 2 with 1 or 2 or 4 or 5, uv with 7, and assign colour 2 to u 1 u. Hence {φ(w 1 t), φ(w 2 z 1 )φ(w 2 z 2 ), φ(z 1 s), φ(z 2 r)} = {1, 2, 3, 4, 5}. Observe that 3 ∈ {φ(tt 1 ), φ(tt 2 )}.

x x 1 x 2 y y 1 y 2 u 1 u 2 u v w w 1 t t 1 t 2 w 2 z 1 z 2 s s 1 s 2 r r 1
Otherwise we can permute the colours of vw and ww 1 , and assign colour 3 to u 1 u. Hence, without loss of generality we can assume φ(tt 1 ) = φ(z 1 s) = 3. Moreover, we prove that φ(tt 2 ) = φ(z 2 r). By contradiction, assume that φ(z 2 r) = α = φ(tt 2 ) (α ∈ {1, 2, 4, 5}). We recolour ww 1 with α, uv with 6, and assign 2 to u 1 u. Now let us uncolour uv and assign colour 2 to u 1 u. Observe that 7 ∈ {φ(ss 1 ), φ(ss 2 )}. Otherwise we can permute the colours of ww 2 and w 2 z 1 , and assign colour 7 to uv. Observe that φ(w 1 t) ∈ {φ(ss 1 ), φ(ss 2 )}. Otherwise we use φ(w 2 z 1 ) to recolour ww 1 , we recolour w 2 z 1 with φ(w 1 t) (recall that {φ(tt 1 ), φ(tt 2 )} = {φ(z 1 s), φ(z 2 r)}), and assign colour 6 to uv. It follows that {7, φ(w 1 t)} = {φ(ss 1 ), φ(ss 2 )} (φ(w 1 t) = 6).

Finally we permute the colours of w 2 z 1 and ww 1 and assign 6 to uv. A contradiction.

5.c Suppose w 2 is a light 3-vertex as depicted in Figure 6. Let us uncolour uv and assign to u 1 u colour 2. If the permutation of the colours of ww 2 and w 2 z 2 is possible, then uv can be recoloured with 7. Hence φ(rr 1 ) = 7. Now we uncolour vw and assign colour 3 to uv. Observe that: {φ(w 1 t), φ(tt 1 ), φ(tt 2 )} = {φ(z 1 s 1 ), φ(z 1 s 2 ), φ(z 2 r)} By contradiction, let us suppose that there exists an α ∈ {φ(w 1 t), φ(tt 1 ), φ(tt 2 )} \ {φ(z 1 s 1 ), φ(z 1 s 2 ), φ(z 2 r)}. Recall α ∈ {1, 2, 3, 4, 5} and φ(w 2 z 2 ) = 3. We colour vw with 7, assign colour φ(w 2 z 2 ) to ww 2 , and recolour w 2 z 2 with α.

x x 1 x 2 y y 1 y 2 u 1 u 2 u v w w 1 t t 1 t 2 w 2 z 1 z 2 s 1 s 2 r r 1 r 2 r 3
Finally we permute the colours of ww 1 and w 2 z 2 , assign colour 6 to uv and colour 3 to vw.

The discharging rules are defined as follows:

(R1) Every 3 3 -vertex gives 1 6 to each adjacent good 2-vertex. (R2) Every 3 2 -vertex and 3 1 -vertex gives 1 4 to each adjacent good 2-vertex if this 2-vertex is not adjacent to a 3 3 -vertex.

(R3) Every 3 0 -vertex gives 1 12 to each adjacent 3 2 -vertex if any. (R4) Every 3 1 -vertex u gives 1 12 to each adjacent 3 2 -vertex v if v has a 2-neighbour w adjacent to a 3 3 -vertex.

(R5) Every 3-vertex gives 1 3 to each adjacent 2-vertex which is a neighbour of 3 3 -vertex. (R6) Every 3-vertex gives 1 2 to each adjacent bad 2-vertex.

Let v ∈ V (H) be a k-vertex. By Claim 4.1, k ≥ 2.
Case k = 2. Observe that ω(v) = -1 2 . Suppose v is a good 2-vertex. If v is adjacent to a 3 3 -vertex, then v cannot be adjacent to another 3 3 -vertex by Claim 4.4. Hence, ω * (v) ≥ - 1 2 + 1 × 1 6 + 1 × 1 3 = 0 by (R1) and (R5). If v is not adjacent to a 3 3 -vertex, then

ω * (v) ≥ -1 2 + 1 × 1 4 + 1 × 1 4 = 0 by (R2). Suppose v is bad. Vertex v is adjacent to one 3-vertex by Claim 4.2. Hence, ω * (v) = -1 2 + 1 × 1 2 = 0 by (R6). Case k = 3. Observe that ω(v) = 1
2 . We have the following cases for v:

• Vertex v is
(v) ≥ 1 2 -1 × 1 4 + 1 × 1 12 -1 × 1 3 = 0 by (R2), ( R3
(v) ≥ 1 2 -1 × 1 2 = 0 by (R6). Suppose u is a good 2-vertex. Let w be the other neighbour of u (d(w) = 3). If w is a 3 3 -vertex, then ω * (v) ≥ 1 2 -2 × 1 12 -1 × 1 3 = 0 by (R4) and (R5). If w is not a 3 3 -vertex, then ω * (v) ≥ 1 2 -2 × 1 12 -1 × 1 4 > 0 by (R2) and (R4). • Vertex v is a 3 0 -vertex. Hence, ω * (v) ≥ 1 2 -3 × 1 12 > 0 by (R3).
This completes the proof.

Third part

Let H be a counterexample to Theorem 2.3 minimizing |E(H)| + |V (H)|: H is not strong edgecolourable with eight colours, mad(H) < 8 3 and for any edge e, χ ′ s (He) ≤ 8. One can assume that H is connected; otherwise, by minimality of H, we can colour each connected component independently. Recall that ω(x) = d(x) - 8 3 .

Claim 5. The minimal counterexample H to Theorem 2.3 satisfies the following properties:

1. H does not contain 1 --vertices.

2. H does not contain two adjacent 2-vertices.

3.

H does not contain a 3-vertex adjacent to three 2-vertices.

4.

H does not contain a 2-vertex adjacent to two 3 2 -vertices.

5.

H does not contain a 3-vertex adjacent to a 3 2 -vertex and a 2-vertex.

6.

H does not contain a 3-vertex adjacent to two 3 2 -vertices.

Claims 5.1 to 5.4 are proved in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF]. Before proving Claims 5.5 and 5.6, we need to introduce some definitions and notations. Let φ be a partial strong 8-edge-colouring of H. For an edge uv, we denote by P C φ (uv) the set of permissible colours that would extend φ to uv. Let SC(N 1 (uv)) be the set of colours used by edges at distance 1 from uv. Proposition 1. Suppose H contains a 3 2 -vertex x. Let u and r be its adjacent 2-neighbours, and let y be its adjacent 3-neighbour. Also let v and s be the other neighbours (distinct from x) of u and r respectively. Finally let z and t be the other neighbours of y (distinct from x).

Consider φ a strong 8-edge-colouring of H ′ = (V (H), E(H) \ {xy, xu, uv, xr, rs}). Then φ satisfies the following:

P1. P C φ (uv) ∩ P C φ (rs) = ∅. P2. {φ(zy), φ(yt)} ∩ (P C φ (uv) ∪ P C φ (rs)) = ∅. P3. P C φ (xy) ⊆ P C φ (uv) ∪ P C φ (rs). P4. SC(N 1 (uv)) = SC(N 1 (rs)). P5. |P C φ (uv)| = 2 = |P C φ (rs)|. P6. SC(N 1 (uv)) ∩ {φ(zy), φ(yt)}) = ∅.

Proof

In the following we prove the proposition for each of the items. P2. By contradiction, assume that φ(zy) ∈ P C φ (uv). We colour uv with φ(zy). Then we colour xy (|P C φ (xy)| ≥ 2; hence it remains at least one colour). We colour sequentially rs (at least one available colour), xr (at least two available colours, since zy and uv have the same colour), and ux (at least one available colour, again zy and uv have the same colour). To summarize Proposition 1 one can assume without loss of generality that:

P C φ (uv) = {1, 2}, P C φ (rs) = {3, 4}, φ(zy) = 5, φ(yt) = 6, SC(N 1 (uv)) = SC(N 1 (rs)) = {7, 8}, P C φ (xy) ⊆ {1, 2, 3, 4}.
Now we prove the remaining parts of the claim.

Proof of Claim 5.5. This follows from the previous discussion in Proposition 1. By contradiction suppose t is a 2-vertex. Observe that the edge yt is coloured with α and has also an other available colour, say β (at most six other coloured edges at distance at most 2). Now β / ∈ P C φ (uv) ∪ P C φ (rs). Otherwise we permute α and β, and this contradicts P2. It suffices then to colour xy with β, the edges uv and ux with the colours of P C φ (uv), and the edges rs and xr with the colours of P C φ (rs). This extends φ to whole H.

Proof of Claim 5.6. By contradiction, suppose H contains a 3-vertex y adjacent to two 3 2 -vertices x 1 and x 2 . Let u i and r i be the two 2-neighbours of x i (i = 1, 2). Finally let v i and s i be the two other neighbours of u i and r i respectively (i = 1, 2). Consider H ′ = (V (H), E(H) \ {yx 1 , x 1 u 1 , u 1 v 1 , x 1 r 1 , r 1 s 1 }). By minimality of H, H ′ admits a strong 8-edge-colouring φ. By the previous discussion and without loss of generality one • Assign φ(xz) = φ(yz) and recolour yz with a free colour.

• Assign φ(xz) = φ(xy) and recolour xy with a free colour. This is a contradiction.

6.

Let ztu be such a path and y and v be the 2-vertices neighbours of z and u respectively.

Let x be the neighbour of y distinct from z and w be the neighbour of v distinct from u. By Claims 6.1, 6.2 and 6.3, x and w are 3-vertices. By Claims 6.3 and 6.4, t is a 3 0 -vertex. Let z 1 , t 1 and u 1 be the neighbours of z, t and u respectively. Since H has no triangles (by Claim 6.5), we have the configuration depicted in Figure 7. Note that in H there might exist edges z 1 t 1 , t 1 u 1 or z 1 u 1 and the representation of the given figure is a general one.

x 1 x 2 x y z t u v w z 1 z 2 z 3 t 1 t 2 t 3 u 1 u 2 u 3 w 1 w 2 Figure 7:
The configuration of Claim 6.6

Let H ′ = Hy. By minimality of H, H ′ can be strongly edge-coloured with at most nine colours. Let us consider such a colouring φ. We show how to extend φ to H. In order to complete the colouring of H one need to assign a colour to xy and yz. By counting the number of edges in N 2 (xy), it is easy to see that there is at least one colour left for xy, so we assign it to this edge. Now, if there is a colour left for yz, then we are done. Therefore, since |N 2 (yz)| = 9, all the colours of 9 must appear exactly once in N 2 (yz) and without loss of generality we can fix the colours of all edges of N 2 (yz) as depicted in Figure 8.

x 1 x 2 x y z t u v w z 1 z 2 z 3 t 1 t 2 t 3 u 1 u 2 u 3
Observe that {5, 6, 7, 9} ⊆ SC(N 2 (xy)) as otherwise one could recolour xy with one of these colours and assign φ(yz) = 1. Therefore, all edges incident to x 1 and x 2 for which we did not fix a colour yet, must have distinct colours from the set {5, 6, 7, 9}. If one could recolour tu with 1, 2, 3, 5 or 6 then yz could be coloured 9 which is impossible. Hence {1, 2, 3, 5, 6} ⊆ SC(N 2 (tu)). Observe that t cannot be neither x 1 nor x 2 as none of the edges incident to t is coloured 2 or 3. Also, since u is adjacent to v which is a 2-vertex, by Claim 6.4 u cannot be neither x 1 nor x 2 . Therefore, if one could permute the colours of tu and zt, then 8 would not belong to SC(N 2 (xy)) any more, thus xy could be recoloured with 8 and yz could be assigned colour 1. Therefore, 8 ∈ {φ(u 1 u 2 ), φ(u 1 u 3 ), φ(vw)}.

Observe that recolouring zz 1 with 2 or 3 must not be possible as otherwise colour 4 could be used for yz to complete the colouring of H. Hence out of all the edges incident to z 2 and z 3 , two of them must be coloured 2 and 3 respectively. Let us uncolour edges xy, zz 1 , zt and tu. We claim that it is not possible to assign colour 4 to tu. Indeed, if tu could be coloured with 4, then we assign φ(tu) = φ(xy) = 4 and by using the fact that two out of all the edges incident to z 2 and z 3 must be coloured 2 and 3 respectively, one of the following assignments of colours would be valid:

• φ(yz) = 1, φ(zz 1 ) = 9 and φ(zt) = 8.

• φ(yz) = 9, φ(zz 1 ) = 1 and φ(zt) = 8.

• φ(yz) = 1, φ(zz 1 ) = 8 and φ(zt) = 9.

Therefore, tu cannot be assigned colour 4 and we must have the following statement:

{φ(t 1 t 2 ), φ(t 1 t 3 ), φ(uu 1 ), φ(u 1 u 2 ), φ(u 1 u 3 ), φ(uv), φ(vw)} = {1, 2, 3, 4, 5, 6, 8} (⋆)
Observe that in (⋆) both sets have the same cardinality and hence φ(t 1 t 2 ), φ(t 1 t 3 ), φ(uu 1 ), φ(u 1 u 2 ), φ(u 1 u 3 ), φ(uv), φ(vw) are pairwise distinct and this implies that there is no edge between t 1 and u 1 .

Consider the edge uv. Since at the beginning of the proof we have fixed φ(tt 1 ) = 7, φ(zt) = 8 and φ(tu) = 9, obviously φ(uv) ∈ 6 .

We distinguish the following cases for φ(uv):

(a) Suppose φ(uv) ∈ {1, 2, 3, 5, 6}. We will denote this colour a. By (⋆) we know that φ(t 1 t 2 ) = a and φ(t 1 t 3 ) = a. We uncolour uv and do the following assignment of colours: φ(xy) = 1, φ(yz) = 9, φ(zt) = 8 and φ(tu) = a. If we manage to colour uv, then we are done. In order to do this, observe that by (⋆), {9, φ(t

1 t 2 ), φ(t 1 t 3 )} ∩ {φ(uu 1 ), φ(u 1 u 2 ), φ(u 1 u 3 ), φ(vw)} = ∅.
Therefore we could use one of the three colours 9, φ(t 1 t 2 ) or φ(t 1 t 3 ) for uv, distinct from the colours assigned to ww 1 and ww 2 . A contradiction.

(b) We have φ(uv) = 4. Let us come back to the fixed colouring of Figure 8. If one could recolour zt with 2 or 3, then yz could be coloured 8. Therefore, two of the three edges t 1 t 2 , t 1 t 3 and uu 1 must be coloured with 2 and 3 respectively. Without loss of generality we can assume that φ(t 1 t 2 ) = 2. Moreover, by (⋆) φ(uv) ∈ {φ(t 1 t 2 ), φ(t 1 t 3 )} = {2, φ(t 1 t 3 )}, which means that {φ(ww 1 ), φ(ww 2 )} = {2, φ(t 1 t 3 )} and without loss of generality we have φ(ww 1 ) = 2. Now, we uncolour zz 1 , zt, uv and assign φ(xy) = φ(tu) = 4. We obtain a valid partial stong edge-colouring of the configuration as depicted in Figure 9. Since φ(t 1 t 3 ) = 9 and none of the other edges of N 2 (uv) is coloured 9, we assign φ(uv) = 9.

x 1 x 2 x y z t u v w z 1 z 2 z 3 t 1 t 2 t 3 u 1 u 2 u 3 w 1 w 2 4
We claim that out of all edges incident to z 2 and z 3 , two of them must be coloured with 1 and 9. Indeed, if it is not the case then by assigning φ(zt) = 8, we could assign either φ(zz 1 ) = 1 and φ(yz) = 9 or φ(zz 1 ) = 9 and φ(yz) = 1 and we would be done. Therefore, four edges incident to z 2 and z 3 except z 1 z 2 and z 1 z 3 must have distinct colours which are namely 2, 3, 1 and 9. If none of the edges t 1 t 3 and uu 1 is coloured 1 then one of the following assignments of colours would be a valid strong edge-colouring:

• φ(yz) = 1, φ(zt) = 8 and φ(zz 1 ) = 9.

• φ(yz) = 9, φ(zt) = 8 and φ(zz 1 ) = 1.

• φ(yz) = 9, φ(zt) = 1 and φ(zz 1 ) = 8.

Therefore, one of the edges t 1 t 3 and uu 1 must be coloured 1. On the other hand, as proved previously, one of these edges must be coloured 3. Therefore, {φ(t 1 t 3 ), φ(uu 1 )} = {1, 3}. Recall from the previous paragraph that in N 2 (zz 1 ), none of the edges is coloured 7. We recolour zz 1 with 7 and uncolour edges tt 1 and tu. Observe that by (⋆) 7 ∈ {φ(uu 1 ), φ(u 1 u 2 ), φ(u 1 u 3 ), φ(vw), φ(ww 1 ), φ(ww 2 )}, so we recolour uv with 7. Moreover, we assign colour 1 to yz and obtain the partial strong edge-colouring of the configuration as depicted in Figure 10. In order to finish the colouring of H we must assign colours to zt, tt 1 and tu. We know that φ(t 1 t 3 ) ∈ {1, 3} and φ(t 1 t 2 ) = 2. Let us consider temporarily the colouring given in Figure 8. If one could recolour edge tt 1 with 5 or 6, then colour 7 could be assigned to yz which implies that out of all the edges incident to t 2 and t 3 , two of them must be coloured 5 and 6 respectively. Applying these to the colouring given in Figure 10, we conclude that one of the following assignments of colours is valid:

• φ(zt) = 8, φ(tt 1 ) = 4 and φ(tu) = 9.

• φ(zt) = 8, φ(tt 1 ) = 9 and φ(tu) = 4.

• φ(zt) = 9, φ(tt 1 ) = 8 and φ(tu) = 4.

Optimality

In [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF], the question about the optimality of the bounds on the strong chromatic index of subcubic graphs in terms of maximum average degree was raised. Let f (r) = inf{mad(G) | χ ′ s (G) > r}. It was proved that: The authors provided graphs reaching the upper bounds for f (6), f (7) and f (9), as depicted in Figure 11.

f (6) ≤
By Theorem 2, we have: Hence the upper bounds on the maximum average degree for f (6), f (7) and f (9) are best possible. Although, we improved the lower bound for f [START_REF] Fouquet | Strong edge-colorings of graphs and applications to multi-k-gons[END_REF] given in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF] from 13 5 to 8 3 , we did not manage to find a better upper bound. The problem of finding this value is even more challenging since till now we do not have an example of subcubic graph G having χ ′ s (G) = 9 and mad(G) < 20 7 .

(a) A graph G with mad(G) =

Proof of Theorem 4

We prove Theorem 4 by contradiction. Suppose the statement is not true and let H be a counterexample minimizing |V (H)| + |E(H)|. We will prove some structural properties of H in order to show that H does not exist.

In the following we use Claim 6 of the proof of Theorem 2.4 as the proof of this claim remains valid within the hypothesis of Theorem 4.

Proof

Suppose there exists such a cycle C as depicted in Figure 12. Observe that x, z, t, u, v, x 1 , z 1 , t 1 , v 1 are 3-vertices by Claims 6.2, 6.3, 6.4 and u 1 is a 3-vertex by Claim 6.6.

Figure 1 :

 1 Figure 1: The prism P has χ ′ s (P ) = 9

2 .

 2 H does not contain a path uvw where u, v and w are 2-vertices.

3 .

 3 H does not contain a 3-vertex adjacent to two 2-vertices one of them being bad.

4 .

 4 H does not contain two 3 3 -vertices having a 2-vertex as a common neighbour.5. H does not contain a 3 3 -vertex u with one of the neighbours, say v, adjacent to a 3 2 -vertex w having as neighbours a 2-vertex w 1 and a 3-vertex w 2 , such that: (a) either w 1 is adjacent to a 3 3 -vertex. (b) or w 2 is a 3 2 -vertex.

Figure 3 :

 3 Figure 3: A fixed precolouring of the configuration of Claim 4.5

Figure 4 :

 4 Figure 4: The configuration of Claim 4.5.a

Figure 5 :

 5 Figure 5: The configuration of Claim 4.5.b

Figure 6 :

 6 Figure 6: The configuration of Claim 4.5.c

  adjacent to three 2-vertices. By Claim 4.3 these 2-vertices are good. Moreover, by Claim 4.4 none of these 2-vertices is adjacent to another 3 3 -vertex. Hence, ω * (v) = 1 2 -3 × 1 6 = 0 by (R1). • Vertex v is adjacent to exactly two 2-vertices. By Claim 4.3, none of these 2-vertices is bad. Suppose that none of these 2-vertices are adjacent to a 3 3 -vertex. Hence, ω * (v) ≥ 1 2 -2 × 1 4 = 0 by (R2). Assume now that one of the 2-vertices adjacent to v is adjacent to a 3 3 -vertex (note that among the 2-vertices adjacent to v, at most one can be adjacent to a 3 3 -vertex by Claim 4.5.a). Hence v cannot be adjacent to a 3 2 -vertex by Claim 4.5.b. Then, v must have either a 3 1 -vertex or a 3 0 -vertex as a neighbour. Hence, ω *

  ) (or (R4)) and (R5).• Vertex v is adjacent to exactly one 2-vertex u. If u is a bad 2-vertex, then by Claim 4.5.c, v cannot be adjacent to a 3 2 -vertex w which has a 2-neighbour y adjacent to a 3 3 -vertex. Hence, ω *

P1.

  Suppose P C φ (uv) ∩ P C φ (rs) = ∅. Let α be a colour of the intersection. First we colour uv and rs with α, then we colour xy (|P C φ (xy)| ≥ 2 ; hence it remains at least one colour). Finally we colour ux (|SC(N 2 (ux))| ≤ 7) and xr (|SC(N 2 (ux))| ≤ 8, but colour α is repeated twice).

P3.

  By contradiction. Observe that |P C φ (uv)| ≥ 2. Let α, β ∈ P C φ (uv). Similarly, let γ, λ ∈ P C φ (rs). Finally let ζ ∈ P C φ (xy) \ (P C φ (uv) ∪ P C φ (rs)). Assign ζ to xy, α to uv, β to ux, γ to rs. Finally, by P1 and P2 we can assign colour λ to xr. P4. By contradiction. Colour first xy, then uv and rs. Count the number of available colours for ux and xr. If one of them has two available colours, then we colour it the last. So each has one available colour. Suppose these two colours are the same. Then we have SC(N 1 (uv)) = SC(N 1 (rs)). P5. By contradiction suppose |P C φ (uv)| ≥ 3 and α, β, γ ∈ P C φ (uv). Suppose P C φ (xy) P C φ (uv). Colour first xy with a colour that does not appear in P C φ (uv), then rs. Assign α to uv, β to ux, and γ to xr (possible by P1, P2 and P4). Now suppose that P C φ (xy) ⊆ P C φ (uv) and P C φ (xy) contains α, β. Colour xy with α, ux with β, uv with γ, xr and rs with the colours of P C φ (rs) (that is possible by P1 and P2). P6. If not true one can colour sequentially xy, uv, rs, xr, ux.

Figure 8 :

 8 Figure 8: The initial fixed colouring of the edges of the configuration of Claim 6.6. Edge yz is the only non-coloured edge.

Figure 9 :

 9 Figure 9: Case (b) of the proof of Claim 6.6. The dashed edges are not coloured.

Figure 10 :

 10 Figure 10: A partial strong edge-colouring of the configuration of Claim 6.6. The dashed edges are not coloured.

7 3

 7 and χ ′ s (G) > 6.(b) A graph G with mad(G) = 5 2 and χ ′ s (G) > 7.(c) A graph G with mad(G) = 20 7 having χ ′ s (G) > 9.

Figure 11 :

 11 Figure 11: Graphs proving the optimality of the bounds of parts 1, 2 and 4 of Theorem 2.

Claim 7 .

 7 H has no 6-cycle C = xyztuvx where y is a 2-vertex.

  4. H does not contain a path uvw where u, v and w are 2-vertices.5.H does not contain a path uvw where u, v and w are three light 3-vertices.ProofSuppose H contains a triangle xyz, where x is a light 3-vertex and let x 1 be the 1-vertex neighbour of x. By minimality of H, the graph Hxx 1 can be strongly edge-coloured with at most six colours. Since |N 2 (xx 1 )| ≤ 5, every colouring of Hxx 1 using the minimum number of colours can be extended to H.

	Claim 2. The minimal counterexample H to Theorem 2.1 satisfies the following properties:
	1. H does not contain a triangle xyz, where x is a light 3-vertex.
	2. H does not contain a path stuvw where s, t, v and w are four light 3-vertices, u is a 3-vertex
	adjacent to a light 3-vertex x.

  2 minimizing |E(H)| + |V (H)|: H is not strong edge-colourable with seven colours, mad(H) < 5 2 , and for any edge e, χ ′ s (He) ≤ 7. Recall that ω(x) = d(x) -5 2 . One can assume that H is connected; otherwise, by minimality of H, we can colour each connected component independently. In this subsection a 3-vertex adjacent to a bad 2-vertex is a light 3-vertex. Otherwise it is a heavy 3-vertex. Claim 4. The minimal counterexample H to Theorem 2.2 satisfies the following properties:

1. H does not contain 1 --vertices.

$ Partially supported by ANR-NSC Project GRATEL -ANR-09-blan-0373-01 and NSC99-2923-M-110-001-MY3

can assume that P C φ (u 1 v 1 ) = {1, 2}, P C φ (r 1 s 1 ) = {3, 4}, φ(zy) = 5, φ(yx 2 ) = 6, SC(N 1 (u 1 v 1 )) = SC(N 1 (r 1 s 1 )) = {7, 8}, P C φ (yx 1 ) ⊆ {1, 2, 3, 4}.

Hence observe that if we can change the colour of yx 2 , then we will be able to extend the colouring (by P2 or P6). To do this uncolour x 2 r 2 . Recolour yx 2 with an available colour distinct from 6. Colour x 2 r 2 . We are done.

We apply now a discharging procedure with the following rules:

(R) Every 3-vertex gives 1 3 to each adjacent 2-vertex and to each adjacent 3 2 -vertex.

Let v ∈ V (H) be a k-vertex. By Claim 5.1, k ≥ 2.

Case k = 2. Observe that ω(v) = -2 3 . By Claim 5.2, the neighbours of v have degree 3. Hence v receives twice 1 3 by (R), and so ω

3 . We have the following cases for v: • If v is not adjacent to any 2-vertices, then v is adjacent to at most one 3 2 -vertex by Claim 5.6, and so gives at most 1 3 by (R) ; it follows ω * (v) ≥ 1 3 -1 3 = 0. • If v is adjacent to exactly one 2-vertex, then its 3-neighbours are not 3 2 -vertices by Claim 5.5. It follows that ω 1 3 from its 3-neighbour (which is not a 3 2 -vertex by Claim 5.5) and gives 1 3 to each adjacent 2-vertex. Hence ω

• The case where v is adjacent to three 2-vertices does not appear by Claim 5.3. This completes the proof.

Fourth part

Let H be a counterexample to Theorem 2.4 minimizing |V (H)| + |E(H)|. We can assume that H is connected as otherwise, by minimality of H, we can colour each connected component independently. Recall that ω(x) = d(x) -20 7 . We first prove some structural properties of H. Claim 6. The minimum counterexample to Theorem 2.4 does not contain:

1. 1 --vertices.

2. two adjacent 2-vertices.

Proof

The proofs of first four parts are given in [START_REF] Hocquard | Strong edge colouring of subcubic graphs[END_REF]. Let u, v and t be the neighbours of x, y and z respectively (u, v and t being outside the triangle). Let H ′ = Hx. By minimality of H, we have χ ′ s (H ′ ) ≤ 9. Consider a strong edge-colouring φ of H ′ using the minimum number. We show how to extend it to H. We colour xu and xy (in each case there exists a free colour). If we have a colour left for xz, then we are done. Therefore, |N 2 (xz)| = 9 and |SC(N 2 (xz))| = 9, which implies that all edges in N 2 (xz) are assigned pairwise distinct colours. Now, one of the following assignment of colours is possible: This is a contradiction.

The discharging rules are defined as follows:

(R1) Every 3 0 -vertex gives 1 7 to each adjacent 3 1 -vertex. (R2) Every 3 1 -vertex gives 3 7 to its adjacent 2-vertex.

Case k = 2. Observe that ω(v) = -6 7 . By Claims 6.2 and 6.3, v is adjacent to two 3 1 -vertices. Hence, by (R2), ω * (v) = - 6 7 + 2 × 3 7 = 0. Case k = 3. Observe that ω(v) = 1 7 . By Claim 6.3, v can be a 3 1 -vertex or a 3 0 -vertex. Suppose, v is a 3 1 -vertex. By Claim 6.4 and by (R1) and (R2), ω ′ (v) = 1 7 + 2 × 1 7 -3 7 = 0. Suppose now that v is a 3 0 -vertex. By Claim 6.6, v is adjacent to at most one 3 1 -vertex. Then by (R1), ω * (v)

This completes the proof. Consider the graph H ′ = Hy. Consider a strong edge-colouring φ of H ′ using at most nine colours. We will extend φ to H in order to obtain a contradiction. Observe that |SC(N 2 (xy))| ≤ 8, thus there exists a colour left for xy. If we can colour yz, then we are done. Therefore, since |N 2 (yz)| = 9, we must have SC(N 2 (yz)) = 9 and every colour is used exactly once in N 2 (yz). Therefore, we claim that |SC(N 2 [xy])| = 9 as otherwise one could recolour xy with another colour and obtain a free colour for yz. Without loss of generality we can assume that φ(zt) = 1, φ(zz 1 ) = 2, φ(xx 1 ) = 3, φ(vx) = 4, φ(uv) = 5, φ(vv 1 ) = 6, φ(x 1 x ′ 1 ) = 7, φ(x 1 x ′′ 1 ) = 8 and φ(xy) = 9. Since SC(N 2 (yz)) = 9 we have {φ(tu), φ(tt 1 ), φ(z 1 z ′ 1 ), φ(z 1 z ′′ 1 )} = {5, 6, 7, 8}. Observe that since 5 ∈ SC(N 2 (tu)) and 5 ∈ SC(N 2 (tt 1 )), without loss of generality we can assume that φ(z 1 z ′ 1 ) = 5. Also, 6 ∈ SC(N 2 (tu)) and therefore φ(tu) ∈ {7, 8}. Since colours 7 and 8 are fixed only on edges x 1 x ′ 1 and x 1 x ′′ 1 respectively, we can assume without loss of generality that φ(tu) = 7 and therefore {φ(tt 1 ), φ(z 1 z ′′ 1 )} = {6, 8}. Figure 13 shows the unique colouring (up to permutation) of the edges described previously.

We claim that one of the edges

must have the same colour as the edge zt (colour 1 in Figure 13). Otherwise, one could change the colour of vx to the colour of zt and colour yz with 4. Similarly, 2 ∈ {φ(v 1 v ′′ 1 ), φ(uu 1 )} (we can assign 2 to vx and 4 to yz). Observe that one can use the same argument conversely (by trying to assign to tz the colour of vx) by recalling from the previous paragraph that {φ(tt 1 ), φ(z 1 z ′′ 1 )} = {6, 8}. Hence, we conclude that one of the edges t 1 t ′ 1 or t 1 t ′′ 1 , say t 1 t ′ 1 , must have the same colour as the edge vx (colour 4 in Figure 13). If it is possible to permute the colours of edges uv and vx, one could obtain a free colour (colour 4) for yz, thus either uu ′ 1 or uu ′′ 1 must have the same colour as vx (colour 4 in Figure 13). Without loss of generality φ(u 1 u ′ 1 ) = 4. If it is possible to permute the colours of edges tu and uv (7 and 5 respectively), then one could obtain a free colour for yz. Hence either φ(v 1 v ′′ 1 ) = 7 or φ(t 1 t ′′ 1 ) = 5 (or both).

1. Suppose φ(v 1 v ′′ 1 ) = 7. Hence φ(uu 1 ) = 2. If one can permute the colours of tu and zt, such that tu is assigned colour 1 and zt is assigned colour 7, then xy could be recoloured with 1 and colour 9 would be free for yz. Hence φ(u 1 u ′′ 1 ) = 1. But now it is possible to permute the colours of xy and uv and to use colour 9 for yz. A contradiction.

2. Suppose φ(t 1 t ′′ 1 ) = 5. If it is possible to change the colour of edge zt (which is 1) to the colour of the edge xx 1 (which is 3), then yz could be coloured with 1. Hence φ(uu 1 ) = 3 and therefore, φ(v 1 v ′′ 1 ) = 2. By permuting the colours of edges vx and xy (4 and 9 respectively) and by recolouring zt with 9, we can colour yz with 1. A contradiction. Consider now the graph H 1 obtained from H by replacing each path of two edges xyz, where y is a 2-vertex and x, z are 3-vertices, by an edge xz. Clearly, H 1 is planar. By Claim 6.5 H has no triangle and since it does not contain an induced 4-cycle, H 1 is simple. Moreover, since it has no 1 --vertices (Claim 6.1) and no two adjacent 2-vertices (Claim 6.2), H 1 is 3-regular. Therefore, H 1 must contain a face of length at most 5, say C ′ . Recall that H has girth at least 6, thus by Claim 6.2, Claim 6.3 and Claim 6.4, C ′ cannot be obtained from a cycle of H of length l ≥ 7. Therefore, in H there exists a cycle C of length 6 having a vertex of degree 2 on its boundary. But this is impossible by Claim 7. Hence H cannot exist.

This completes the proof of Theorem 4.


Martine Hennequin
email: martine.hennequin@u-clermont1.fr

Ve ´ronique Moysan

Martine Dorin

Emmanuel Nicolas

Inequalities in Oral Health for Children with Disabilities: A French National Survey in Special Schools

Background: Despite wide recognition that children with disability often have poor oral health, few high quality, controlled results are available.

Method: Twenty-four objective and subjective criteria covering feeding, autonomy, access to dental care, oral hygiene, oral disease, general health and behavior were evaluated in a observational cross-sectional study of 2,487 children with disability (DC group), 4,772 adolescents with disability (DA group) and 1,641 children without disability (NDC group). Five algorithms ranked the subjects according to clinical criteria in three original oral health indices: the Clinical Oral Health Index (COHI), indicating the level of oral health problems, the Clinical Oral Care Needs Index (COCNI) giving dental care need levels, and the Clinical Oral Prevention Index (COPI) determining possible needs in terms of dental education initiatives.

Results: DC-group children presented poorer oral health and had greater needs in both treatment and preventive oral health actions than NDC-group children (OR = 3.97, 95% CI = 3.25-4.86 for COHI; OR = 2.01, 95% CI = 1.77-2.28 for COCNI; OR = 5.25, 95% CI = 4.55-6.02 for COPI). These conditions were worse again in the DA group comparing to the DC group (OR = 3.52, 95% CI = 2.7-4.6 for COHI; OR = 1.52, 95% CI = 1.38-1.69 for COCNI; OR = 1.53, 95% CI = 1.39-1.69 for COPI).

Conclusion:

Clinical indices generated by algorithmic association of various clinical indicators allow sensitive clinical measurement, and in this study demonstrated inequalities in oral health for children with disabilities schooling in institutions. Questions need now to be addressed as to the measures that could be taken to compensate for this situation.

Introduction

Oral health is often considered as a probable source of health inequalities in persons with neuromotor and mental deficiencies. The quality of the evidence base supporting this assumption is not high despite numerous studies reporting poor oral health in patient groups with disabilities. Many studies have no control group, use inappropriate indicators or report a partial evaluation of oral health. The 2001 National Survey of Children with Special Health Care Needs conducted in the USA showed that dental care was the most commonly-reported unmet service need [START_REF] Waldman | Children with special health care needs: results of a national survey[END_REF]. However, none of the clinical data collected through a large sample was able to confirm the parents' declarations. Some studies have aimed to measure only the prevalence of infectious disease, such as carious process or periodontal disease [START_REF] Shaw | The oral health in different groups of adults with mental handicaps attending Birmingham (UK) adult training centres[END_REF][START_REF] Vazquez | Prevalence of dental caries in an adult population with mental retardation in Spain[END_REF][START_REF] Nunn | Dental Disease and current treatment needs in a group of physically handicapped children[END_REF], while others have focused on the occurrence of anatomical deficiencies [START_REF] Oreland | Malocclusions in physically and/or mentally handicapped children[END_REF][START_REF] Fischer-Brandies | Cephalometric comparison between children with and without Down's syndrome[END_REF][START_REF] Hobson | Orthodontic management of orofacial problems in young people with impairments: review of the literature and case reports[END_REF], traumatic disease [START_REF] Shyama | Malocclusions and traumatic injuries in disabled schoolchildren and adolescents in Kuwait[END_REF] or functional incapacity [START_REF] Frazier | Swallow function in children with Down syndrome: a retrospective study[END_REF][START_REF] Spender | An exploration of feeding difficulties in children with Down syndrome[END_REF][START_REF] Santos | Infantile reflexes and their effects on dental caries and oral hygiene in cerebral palsy individuals[END_REF][START_REF] Hennequin | A comparison of chewing indicators between adults with Down syndrome and controls[END_REF]. Oral health is, however, a far more complex concept that encompasses all aspects of health related to the mouth, the jaw, the teeth, the throat and related tissues [START_REF] Locker | Measuring oral health: a conceptual framework[END_REF][START_REF] Mcentee | An existential model of oral health from evolving views on health, function and disability[END_REF]. Self-rated questionnaires on oral health-related quality of life aim to offer a global measure of the concept of health but their use is not feasible by the majority of people with intellectual disability [START_REF] Slade | Development and evaluation of the Oral Health Impact Profile[END_REF][START_REF] Allison | A cross-cultural study of oral health values[END_REF][START_REF] Page | Validation of the Child Perceptions Questionnaire (CPQ 11-14)[END_REF]. Proxy questionnaires have been developed for use with persons presenting special medical conditions [START_REF] Hennequin | Prevalence of oral health problems in a group of individuals with Down syndrome in France[END_REF][START_REF] Trulsson | Living with a child with a severe orofacial handicap: experiences from the perspectives of parents[END_REF], but they remain too specific to be used universally across all disability groups. The lack of appropriate indicators has consequently made it impossible to compare oral health between groups with and without disabilities. This study was thus designed to provide epidemiological data on oral health gathered using original indicators from a representative sample of children and adolescents with disabilities in France.

Method

Database setting

This observational cross-sectional study compared data gathered in the same conditions through two surveys. The design for data base setting is shown in Figure 1. One dataset was taken from a national survey that evaluated oral health in a sample of 6 to 20year-old children and adolescents in special schooling. The second dataset was taken from a regional survey of a nationally representative sample of 6 to 12-year-old children without disabilities in mainstream schooling. The database thus included three groups differentiated by both age and presence of a disability: one group comprising of 6 to 12-year-old children without disability (NDC group), a second group made up of 6 to 12-year-old children with disability (DC group), and a third group comprising of 13 to 20-year-old adolescents and young adults with disability (DA group). Consent for participation was obtained from the school directors, class teachers, parents, and adult subjects. All legal conditions for epidemiological surveys were respected, and the French national commission governing the application of data privacy laws (the 'Commission Nationale Informatique et Liberte ´s') issued approval for both projects.

Children, adolescents and young adults with disability. The sample populations of children and adolescents with disability were derived from the databases of three national health insurance systems. The population comprised of all 74,276 children, adolescents and young adults born between the 1 st October 1984 and the 31 st January 1999 attending one of the 1,325 special schools registered in France.

The sample size was calculated to determine the results with a 99% Confidence Interval and a precision of 61.5% around the calculated value. Theoretical national sample size thus reached 7,373 statistical units. Since the risk of non-response was evaluated at between 25% and 35%, the sample size was raised to 10,000 statistical units. For random selection, all children born on a 4 th , 7 th , 21 st or 27 th day of the month were included. The survey was conducted between October 2004 and January 2005.

Children without disabilities. The sample of children without disabilities comprised the entire population of 2 to 12year-old healthy children attending schools situated in the department of Puy de Do ˆme. This group was devised to be nationally representative, by performing a cluster evaluation design with the school as the intervention unit. The schools were selected on the basis of the following criteria: rural or urban location, socioeconomic status (4 standard groups from underprivileged to highly privileged) and size (more or less than 4 classes) in two school districts (corresponding to a population of 106,088 inhabitants). Twenty two schools were sampled based on these criteria. Comparison between the sample and national data [START_REF]Repe `res et re ´fe ´rences statistiques sur les enseignements[END_REF] is showed in Table 1. Children under 6 years old and children Table 1. Characteristics (expressed as %) of the sample compared to national data [START_REF]Repe `res et re ´fe ´rences statistiques sur les enseignements[END_REF]. The location is based on the INSEE (National Institute for Statistics and Economic Studies) definition (more or less than 2000 inhabitants in the city), the socioeconomic status analysis is based on the standards of the education department (from 1: privileged to 4: underprivileged). There is no national data for the location, so the regional data were used. doi:10.1371/journal.pone.0002564.t001

AND having no criteria that had a social impact:

No halitosis and No drooling and No anterior tooth with a fractured, unrestored crown 1 OR Having no criteria that had a medical impact:

Existence of one or more problems with a low to a moderate impact on health

No mucosal lesion on lips, tongue or jaw or Absence of dental plaque (Green and Vermillon index = 0 for both arches) [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF] or Absence of calculus (Green and Vermillon index = 0 for both arches) [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF] or No gingivitis (Loe and Silness index = 0 for both arches) [START_REF] Lo ¨e | Periodontal disease in pregnancy. I. Prevalence and severity[END_REF] or Having at least one criterion that had a medical impact At least one mucosal lesion on lips, tongue or jaw or Dental plaque (Greene and Vermillon index .0, on a group of teeth or all the teeth of at least one arch) [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF] or Calculus (Greene and Vermillon index .0, on a group of teeth or all the teeth of at least one arch) [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF] or Localized gingivitis (Loe and Silness index .0 on a group of teeth or at least one arch) [START_REF] Lo ¨e | Periodontal disease in pregnancy. I. Prevalence and severity[END_REF] or At least one anterior tooth with a fractured, unrestored crown or One limited anterior edentulous segment (1 or 2 anterior teeth)

or At least one minor posterior edentulous segment (missing all molars and premolars on 1 or 2 half-arches with at least one residual inter-arch dental contact)

or At least one incipient carious lesion, but no developed carious lesion (stage 1 or 2 according to the Eckstrand classification for carious lesions) [START_REF] Ekstrand | Relationship between external and histologic features of progressive stages of caries in the occlusal fossa[END_REF] or Presence of a simple orofacial dysmorphology … regardless of the criteria that had a social impact

2
Having at least one criteria that had an important medical impact

Existence of one or more problems with important to severe impact on health Generalized gingivitis (Loe and Silness index .0 for both arches) [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF] or Missing at least 3 anterior teeth or At least one major posterior edentulous segment (missing all molar and premolars on at least 2 half-arches, without any residual inter-arch dental contact)

who received special schooling time for medical reasons were not included in the database. The survey was conducted between January and May 2005.

Data collection

Investigators. Examination of the children, adolescents and young adults with disability was conducted by 338 salaried dentists belonging to one of the three French national health insurance schemes. The investigator first conducted a structured interview with the child and his or her carer, and then examined the child. Any modification in the child's behavior or any declaration that suggested discomfort or distress led to the evaluation being interrupted. For the group of children without disability, the evaluation was conducted by 7 dentists who collected the data under these same conditions. All investigators underwent a oneday training course in their region prior to starting the study. The course consisted of three hours on the conditions for data collection and three hours on the psychosocial conditions of the population of children with disabilities.

Development of the list of indicators. A initial list of 36 indicators for examination was generated from literature review, interviews with professional experts in special care dentistry, in special education and with practitioners of the health insurance system. They were descriptions of global health, feeding, autonomy, access to dental care, oral hygiene, oral disease, and behavior. The feasibility of data collection and the clinical and social significance of the indicators were initially tested with a sample of 236 children and adolescents from 27 institutions distributed in 7 regions. Items resulting in a response rate of less than 70% were then deleted from the list that finally included 24 items. External consistency of the 24 item list was evaluated by comparing the prevalence of oral disease in the test group to the values founded in previous studies for different groups of children with disabilities. External consistency was good for food texture [START_REF] Sullivan | Prevalence and severity of feeding and nutritional problems in children with neurological impairment: Oxford Feeding Study[END_REF][START_REF] Hennequin | Prevalence of oral health problems in a group of individuals with Down syndrome in France[END_REF], difficulties in pain communication [START_REF] Hennequin | Pain perception by parents of children with Down syndrome[END_REF][START_REF] Hennequin | Pain expression and stimulus localization for individuals with Down syndrome[END_REF], halitosis [START_REF] Hennequin | Prevalence of oral health problems in a group of individuals with Down syndrome in France[END_REF] drooling [START_REF] Tahmassebi | Prevalence of drooling in children with cerebral palsy attending special schools[END_REF][START_REF] Donnell | Dental findings in 4-, 14-, and 25-to 35-year-old Hong Kong residents with mental and physical disabilities[END_REF], presence of dental plaque, calculus and gingivitis [START_REF] Hennequin | Prevalence of oral health problems in a group of individuals with Down syndrome in France[END_REF][START_REF] Lancashire | The oral hygiene and gingival health of paraplegic inpatients-a cross-sectional survey[END_REF][START_REF] Stabholz | Caries experience, periodontal treatment needs, salivary pH and Streptococcus mutans counts in a preadolescent Down syndrome population[END_REF], missing teeth [START_REF] Maestre | The use of general anaesthesia for tooth extraction in young handicapped adults in France[END_REF][START_REF] Hennequin | Accuracy of estimation of dental treatment needs in special care patients[END_REF], fractured anterior tooth [START_REF] Shyama | Malocclusions and traumatic injuries in disabled schoolchildren and adolescents in Kuwait[END_REF], caries decay [START_REF] Nunn | Dental Disease and current treatment needs in a group of physically handicapped children[END_REF][START_REF] Stabholz | Caries experience, periodontal treatment needs, salivary pH and Streptococcus mutans counts in a preadolescent Down syndrome population[END_REF][START_REF] Shyama | Malocclusions and traumatic injuries in disabled schoolchildren and adolescents in Kuwait[END_REF][START_REF] Muller | The oro-dental status of a population of school children in the southeast of France[END_REF], dental infectious process [START_REF] Hennequin | Accuracy of estimation of dental treatment needs in special care patients[END_REF], severe dysmorphology [START_REF] Franklin | The prevalence of malocclusion in children with cerebral palsy[END_REF], and lack of compliance during oral examination [START_REF] Nunn | Dental Disease and current treatment needs in a group of physically handicapped children[END_REF][START_REF] Gordon | Dental fear anxiety as a barrier to accessing oral health care among patients with special health care needs[END_REF]. Cronbach's alpha was used to assess internal consistency of the list of 24 indicators for oral health evaluation. It was shown that the list was consistent (a = 0.93).

The inclusion criteria for children with disabilities were based on the diagnoses that justified children being orientated towards special schooling. These diagnoses were defined according to standard ICD-10 criteria [START_REF]ICD 10, International Classification for Disabilities, 10 th version[END_REF].

Subject examination. Among the 24 item list, 20 items were objective indicators that were evaluated by the investigator during the oral examination. Children and adolescents in DC and DA groups were examined in the school dispensary in presence of their carer. Children in the NDC group were examined in their classroom in the presence of their teacher. For the evaluation of objective criteria, the investigators used disposable gloves, a mouth mirror and a portable light. Drying teeth and the use of a dental probe, both of which are indicated for caries and periodontal disease screening in the general population [START_REF] Greene | The oral hygiene index: a method of classifying oral hygiene status[END_REF][START_REF] Lo ¨e | Periodontal disease in pregnancy. I. Prevalence and severity[END_REF][START_REF] Ekstrand | Relationship between external and histologic features of progressive stages of caries in the occlusal fossa[END_REF], were prohibited so as to avoid discomfort or injury. Four subjective indicators of oral health were obtained during a structured interview with the carer for each subject with disability, and with the child him or herself for each child without disability.

Stability of the indicators. Considering the vulnerability of the target population, it would have been unethical to build a true sample of children with disability for the calibration of the investigators. A virtual sample was therefore simulated with a set of 144 photos of the mouths of 6 to 20-year-old children and young adults with and without oral disease. The investigators had to evaluate the pictures twice, with a one-week interval.

Internal reliability was verified by paired comparisons of consistency between the two evaluations for all 144 pictures (intra-class correlation coefficients (ICC, r), and kappa coefficients (k)). Among the investigators who evaluated the children and adolescents with disabilities, 269 (79.6%) participated in the reliability test. Test-retest revealed that internal reliability was acceptable for the 144 pictures (mean ICC 95%, r = 0.65; k = 0.49, (p,0.001)). The distribution of the investigators within the range of the ICC values was: r.0.4 for 6 investigators (2.2%); 0.4,r,0.6 for 48 investigators (17.8%); 0.6,r,0.8 for 211 investigators (78.4%); and 0.8,r for 4 investigators (1.5%). External reliability was verified by testing the agreement between the criteria values given for each picture by the group of 269 investigators (ICC 95%, r = 0.63). All 7 investigators examining the group of children without disabilities participated in the reliability test. Test-retest showed that internal reliability was acceptable for the set of 144 pictures (mean 95% ICC, r = 0.74; k = 0.46) and that external reliability was good (95% ICC, r = 0.86).

Data analysis. Indicators of oral health were then associated to produce 3 original indices for global oral health. Initially a series of 3 algorithms were performed using logical association (If… then… else…) to rank the subjects according to the 4 levels of the Clinical Oral Health Index (COHI) (Table 2). A fourth algorithm was then used to rank the subjects according to the 4 levels of the Clinical Oral Care Needs Index (COCNI) (Table 3). Finally,

COHI Values CRITERIA

or At least one developed carious lesion (stage 3 or 4 according to the Eckstrand classification for carious lesions) either on a deciduous or a permanent tooth [START_REF] Ekstrand | Relationship between external and histologic features of progressive stages of caries in the occlusal fossa[END_REF] or At least one infected lesion (presence of an abscess, or a tooth with pulpal exposure, or a fistula)

or Presence of complex orofacial dysmorphology … regardless of the criteria that had a social impact Undetermined At least one undetermined criteria that had a medical impact and regardless of the criteria that had a social impact.

Others conditions by elimination or Having no criteria that had a medical impact but having at least one undetermined criteria that had a social impact. doi:10.1371/journal.pone.0002564.t002

Table 2. Cont.

preventive health or oral health education needs were determined by applying a fifth algorithm that ranked the subjects according to the two levels of the Clinical Oral Prevention Index (COPI) (Table 4). The distributions of the NDC and DC groups across the various levels of the COHI, COCNI and COPI indices were compared to determine whether having a disability is a risk factor for poor oral health. The impact of age on oral health status was determined by comparing the distributions of the DC and DA groups across the different levels of the COHI, COCNI and COPI oral health indices. Odds ratios (OR) were calculated at 95% confidence intervals for inter-group comparisons.

The impact of 69 (untrained) out of 338 (trained) examiners for the DC and NDC group not participating in the test retest exercise, was evaluated by comparing the distributions of the subjects evaluated by untrained and trained examiners across the different levels of the COHI, COCNI and COPI oral health indices.

Results

Descriptive results

A total of 8,401 children, adolescents and young adults with disability were randomly selected among the 1,259 institutions that 2) autism (4.6%), other psychological developmental problems (11.5%), schizophrenia and delusional disorders (2%), other mental and behavioral diseases (6.8%); 3) Down syndrome (9.5%) and other chromosome anomalies (2.4%); 4) developmental disorder (3.1%) and neonatal or maternal disease (3%); 5) epilepsy (1.9%) and other anomalies of the central nervous system (3%); 6) other diseases (3.9%); 7) unfavorable family and social background (1.6%); 8) missing data (0.5%). Systemic diseases requiring oral health monitoring were recorded in both the DC and DA groups (maximum 3 per subject). Epilepsy, congenital cardiac disease, bronchopneumopathy (including asthma), internal prosthesis, immunodeficiency and hematological disease, and diabetes, were recorded for 1027, 410, 287, 32, 32 and 31 subjects, respectively. Others miscellaneous systemic diseases were recorded in 408 cases. There were no distribution-based differences either in medical conditions or in gender between the DC and DA groups.

The NDC population consisted of 1,772 healthy children aged 6 to 12 years old from 22 mainstream schools. Among this group, refusals to participate were received from either parents or teachers of 71 children, evaluation failed for lack of coordination between school staff and investigators for another 56 children, and 4 children were absent from school at the time of evaluation. Hence, 1,641 children without disability aged between 6 and 12 year old were included (862 males, 779 females; mean age6SD: 7.9861.61 years (95%CI = 7.91-8.06)). Gender and age distribution differed significantly between DC and NDC groups with both prevalence of boys (Chi Square test, p,0.001) and mean age being greater in the DC group than in NDC group (Chi Square test, p,0.01).

Oral health status

Subject distributions in terms of oral health criteria and the indices are presented in tables 5 and 6, respectively. Distribution comparisons between the NDC and DC groups showed that more children with disability were rated COHI level 1 or 2 than level 0 (OR = 3.97; 95% CI = 3.25-4.86). Moreover, the number of children for whom some oral health indicators could not be estimated was greater in the DC group than in the NDC group (OR = 2.41; 95% CI = 1.74-3.32). Comparisons of COCNI distributions showed that more children with disability were in need of urgent care or examination (level 3) or non-urgent care (level 2) than those without disability (OR = 2.01; 95%CI = 1.77-2.28). COPI index distribution comparisons showed that more children with disability were in need of preventive oral health care or oral health education than children without disability (OR = 5.25, 95% CI = 4.55-6.02).

COHI index distribution comparisons between the DC and DA groups showed that a higher number of adolescents and young adults were rated COHI level 1 or 2 than level 0 (OR = 3.52; 95% CI = 2.7-4.6). Moreover, the number of subjects who could not be rated due to unspecified criteria was significantly higher in the DA group than in the DC group (OR = 1.3; 95% CI = 1.08-1.56). COCNI index distribution comparisons showed that more adolescents and young adults were in need of urgent care or examination (level 3) or non-urgent care (level ), whereas slightly more younger children were either in need of examination (level 1) or were not in need of care or examination (level 0) than children with disabilities (OR = 1.52; 95% CI = 1.38-1.69). COPI index distribution comparisons showed that adolescents and young adults with disabilities had greater needs for preventive oral health care or oral health education actions than children (OR = 1.53, 95% CI = 1.39-1.69).

A stratified comparison between the DC and NDC groups was performed testing for the impact of gender and age on child distribution between COHI, COCNI and COPI. It was shown that the distribution of children between the DC and NDC groups remained different regardless of gender (Chi Square test, p,0.001, for distribution in COHI, COCNI and COPI) and age for all age classes (Chi Square test, p,0.05 COHI, COCNI and COPI), except for the distribution of 7 to 8 year old children in COPI (Chi Square test, non significant).

The distributions of the children who did not participate in the evaluation for refusal for participation, absence from school or death did not differ between the group of 269 trained investigators and those 69 untrained investigators (Chi Square test, non significant). A total of 1343 subjects with disabilities were evaluated by the 69 untrained examiners (Table 7) The distributions across the different levels of COHI, COCNI and COPI of the 395 DC group children who were evaluated by the 69 untrained examiners did not differ from those of the other 2092 DC group children who were evaluated by the 269 trained examiners. The distributions across the oral health indices of the 948 adolescents in the DA group who were evaluated by the Table 5. Subject distribution among the oral health criteria for the three groups of children or adolescents. { absence of molars or premolars in at least one quarter of the mouth.

{ stage 1 or 2 according to the Eckstrand classification for carious lesions without stage 3 or 4 caries, either on a deciduous or permanent tooth [START_REF] Ekstrand | Relationship between external and histologic features of progressive stages of caries in the occlusal fossa[END_REF].

1 stage 3 or 4 according to the Eckstrand classification for carious lesions either on a deciduous or permanent tooth [START_REF] Ekstrand | Relationship between external and histologic features of progressive stages of caries in the occlusal fossa[END_REF].

I

presence of an abscess, or a tooth with pulp exposure, or a fistula related to dental disease. ** Four groups of malocclusion were defined: G1: Complete overjet of one or more than one tooth. G2: 1) Overjet of 6 mm or more than 6 mm; or 2) Labial or buccal openbite concerning three pairs of teeth or more than three; or 3) Significant or considerable crowding or overcrowding in labial or buccal arch sectors. G3: 1) Reverse overbite of at least one upper incisor or reverse overbite of at least one lower incisor; or 2) reverse overbite of post-canine teeth on one side or overbite of a complete or half arch buccal sector, provoking deflection or deviation of the mandible on contact through the intercuspal position or 3) overcoupled teeth. G4: 1) Deep overbite of front teeth associated with an overjet; or 2) Bilateral reverse overbite associated with an early deviating contact during the mandibular closing phase.

Malocclusions of types G1 and G3 are considered as simple when not associated with malocclusions pertaining to G2 or G4. Malocclusions of types G2 and G4 and those associated with other malocclusions are considered as complex.

{{ according to the modified Venham scale [START_REF] Venham | Children's response to sequential dental visits[END_REF] score $1. The modalities of subject distribution among the criteria were dichotomized for simplification. n: number of subjects for whom the criteria was evaluated; Yes: percentage of subjects experiencing the disorder. doi:10.1371/journal.pone.0002564.t005 untrained examiners differ significantly from those of the 3824 other DA group children who were evaluated by the trained examiners for COHI (Chi square test, p,0.005) and COCNI (Chi square test, p,0.001). There were fewer subjects in both level 2 for COHI and level 3 for COCNI among the DA group subjects who were evaluated by the untrained examiners. The distribution across COPI did not differ significantly depending on whether the examiners were trained or not.

Discussion

This is the largest cross-sectional study to report oral health status for children and adolescents with disability. It demonstrates that the prevalence of poor oral health is increased in children with disability than in children without, and that this situation worsens with age. This study is also the first attempt to produce an original biopsychosocial indicator for oral health. The construct validity of the list of indicators could discriminate between subjects by age and presence of a disability. The concept of a clinical index generated by an algorithmic association of various clinical indicators is completely new in oral health, and offers a sensitive clinical measurement that could be used transversally in different populations.

Improving oral health is a specific concern for individuals with disability as oral health has both local and systemic consequences. Poor oral health is a factor for co-morbidity when associated with systemic disease. It increases the risk of infectious complications for patients presenting systemic diseases such as congenital cardiac disease, immunodeficiency or diabetes, or those with internal prostheses, and plays a direct role in the aggravation of chronic respiratory disease that is the main cause of mortality in people with disability [START_REF] Mojon | Oral health and respiratory infection[END_REF][START_REF] Yoneyama | Oral Care Working Group Oral care reduces pneumonia in older patients in nursing homes[END_REF][START_REF] Adachi | Professional oral health care by dental hygienists reduced respiratory infections in elderly persons requiring nursing care[END_REF]. For patients with epilepsy or mental deficiencies, both neurological and behavioral problems may be related to undiagnosed and untreated oral pain. This survey raises questions as to the measures that could be taken to decrease inequalities in oral health for children and adolescents with disability. There are three main strands to improving oral health in this population: improving oral hygiene, defining specific training for dental professionals, and allocating funds to cover dental care access and service utilization [START_REF] Young | Use of health care among adults with chronic and complex physical disabilities of childhood[END_REF]. Oral hygiene decreases bacterial load by eliminating the lung pathogens present on the tongue, gum tissue and other oral mucosa or contained in dental plaque. Persons with disability, however, do not always have the neuromotor abilities required to independently and effectively perform oral hygiene [START_REF] Faulks | A controlled national survey of difficulty encountered by persons with Down syndrome during hygiene and health care[END_REF]. Consequently, care staff and families who help with daily dental hygiene tasks should be targeted for educative programs [START_REF] Frenkel | Oral health care education and its effects on caregivers' knowledge and attitudes: a randomised controlled trial[END_REF][START_REF] Glassman | Preventing dental disease for people with special needs: the need for practical preventive protocols for use in community settings[END_REF]. In some countries, including France, the healthcare system does not currently identify the professionals needed to teach care staff. Training of hygienists and tutoring special care issues during dental education could help to improve oral hygiene and care standards for people with disability [START_REF] Allison | Dental care access among individuals with Down syndrome in France[END_REF].

There are both political and economic choices to be made before specific funds can be allocated for this population. It has been shown in the USA that children with the most limited functional ability were 50% less likely to meet the health insurance core outcome than those without limitations [START_REF] Honberg | Assuring adequate health insurance: results of the National Survey of Children with Special Health Care Needs[END_REF]. In France, the national health insurance system does not cover specific oral care procedures for people with disability, despite the fact that the State has declared its obligation to provide administrative facilitators to compensate for disability issues in the 2002 Disability Rights Bill. Other countries, including the USA, are examining the adoption of new standards and studying the continuing obstacles of limited government support for dental services [START_REF] Waldman | Mandating education of dental graduates to provide care to individuals with intellectual and developmental disabilities[END_REF].

There were many potential methodological biases that could undermine this study. The first question is related to the representativity of our sample against national populations of children with and without disabilities. The sample of children and adolescents with disabilities was randomly selected from a child Table 6. Distribution of the children with and without disabilities according to the values of the Clinical Oral Health Index (COHI), the Clinical Oral Care Needs Index (COCNI) and the Clinical Oral Prevention Index (COPI).

Children without disability

Children population in 1279 out of 1325 special schools. In France, the vast majority of children with learning disabilities are schooled in institutions, following a decision by a special commission which evaluates their medical condition. Special schools therefore offer an ideal context in order to gain access to a large national sample of these children. It was however impossible to compare the sample of children and adolescents with disability to the national population of children with disabilities, as we had no information on the population from the 46 institutions that did not consent to participate in the study. In addition we have no demographic information on the population of children with severe disabilities who are schooled either at home, or in ordinary schools. This discrepancy in the constitution of samples cannot be controlled and could induce bias. It was however the only practical way to undertake the study, as it was impossible to constitute a wider sample of children with disabilities in the usual conditions that are respected for epidemiological studies. An even greater degree of difficulty was found in constituting a sample of adolescents and young adults with disabilities. Ethical, political, financial and technical difficulties were barriers that led to abandon the project of comparing the oral health conditions in DA group to those of a control sample.

Secondly, the methodology for the reliability tests was based on photograph-based evaluations rather than on clinical examinations. Compared to a subject based examination, the photos gave a partial view of the subject, reducing him/her to a part of his/her mouth or face. In these conditions, the quality of the computer screens that served for photo evaluation was a factor that might affect the external reliability, in addition to the psychometric characteristics of each individual investigator. Despite these conditions, internal and external reliability remained acceptable.

Thirdly, the examination/interview of children and adolescents with disability was conducted by 338 dentists working for a French national health insurance scheme while those without disability were examined/interviewed by 7 other dentists. In addition, the investigators were not isolated, and independent assessments for both groups cannot be expected. As these conditions could not be modified, we tried to control them by giving the same training to each group of investigators. In particular and in order to limit the psychological impact of contact with children suffering from severe disability on the investigators' evaluation, specific training was provided regarding patients with special needs prior to the survey.

Fourth, a total of 69 out 338 examiners did not participate in the test retest exercise. It was however demonstrated that this point did not alter the distribution across the COHI, COCNI and COPI indices in the DC group children but that it could affect the subjects distribution across COHI and COCNI for the DA group (Table 7). The untrained examiners who did not participate in the test-retest exercise underestimated the severity of the oral health disease and the needs for treatment in the group of adolescents with disabilities. Consequently it could be assumed that the differences between the DA and DC groups would be increased if all the examiners had completed the test-retest exercise. Fifth, among the 24 indicators for examination/interviews, four (coughing often during meals, having recent discomfort or pain, difficulties expressing pain, and being uncooperative during oral examination) were subjectively evaluated using either care staff report for the DC and DA groups, or self report for the NDC groups. The information thus compiled might not be exactly the same in these different conditions. For this reason, these subjective indicators were not included in the items determining the COHI and COCNI indices but featured exclusively in the COPI index.

Despite these limitations, the COHI, COCNI and COPI indices offer sensitive clinical measurements of oral health status in epidemiological surveys. Further developments are needed to increase the field of application of these biopsychosocial indices for oral health.

Figure 1 .

 1 Figure 1. Design for data base setting. doi:10.1371/journal.pone.0002564.g001

  No fractured anterior tooth or No missing anterior tooth or No missing posterior tooth or No dental caries or No infectious disease or No orofacial dysmorphology AND having at least one criteria that had a social impact: Presence of halitosis or Presence of drooling or At least one anterior tooth with a fractured unrestored crown

3

 3 Urgent need for care or examination Marker of local infectious disease During the last three months the child expressed discomfort or pain in his/her mouth and consecutively he/she had no dental visit. or At least one mucosal lesion on lips, tongue or jaw or At least one infected lesion (presence of an abscess, or a tooth with pulp exposure cavity, or a fistula) AND absence of any systemic disease* requiring specific oral health monitoring. Marker of focal infectious disease During the last three months the child expressed discomfort or pain in his/her mouth and consecutively he/she had no dental visit. or Presence of at least one mucosal lesion on lips, tongue or jaw or At least one infected lesion (presence of an abscess, or a tooth with a pulp exposure, or a fistula) or Presence of generalized gingivitis (Loe and Silness index .0 for both arches) AND Existence of a systemic disease requiring specific oral health monitoring* Marker of traumatic lesions During the last three months the child expressed discomfort or pain in his/her mouth and consecutively he/she had no dental visit. or Presence of at least one mucosal lesion on lips, tongue or jaw Marker of oral disease with functional or social consequences During the last three months the child expressed discomfort or pain with his/her mouth and consecutively he/she had no dental visit. 2 Need for care or examination Marker of local infectious disease Presence of calculus or Presence of gingivitis or Presence of at least one anterior tooth with a fractured, unrestored crown or Presence of at least one developed carious lesion. AND Absence of a systemic disease* requiring specific oral health monitoring Marker of focal infectious disease Presence of calculus. or Presence of a localized gingivitis or Presence of at least one anterior tooth with a fractured, unrestored crown or Presence of at least one developed carious lesion. AND Existence of a systemic disease* requiring specific oral health monitoring Marker of traumatic lesions Presence of at least one anterior tooth with a fractured, unrestored crown 1 Need for examination Marker of local infectious disease No dental visit over the last 12 months or Presence of dental plaque or Presence of at least one incipient carious lesion. AND Absence of a systemic disease* requiring specific oral health monitoring Marker of focal infectious disease No dental visit over the last 12 months or Presence of dental plaque or Presence of at least one incipient carious lesion. AND Existence of a systemic disease* requiring specific oral health monitoring Marker of traumatic lesions No dental visit over the last 12 months Marker of oral disease with functional or social consequences No dental visit over the last 12 months or Presence of an anterior edentulous segment from 1 to 6 teeth on at least one arch. or Presence of a posterior edentulous segment for children up to 13 years old) or Presence of untreated severe orofacial dysmorphology 0 No need for care nor examination Other conditions by elimination * Epilepsy, congenital cardiac disease, bronchopneumopathy (including asthma), internal prosthesis, immunodeficiency and hematological disease, or diabetes. doi:10.1371/journal.pone.0002564.t003 agreed to participate. Refusals to participate were declared in 332 cases, absence from the institution at the time of evaluation was recorded in 808 cases, and two children died before the investigator visit. Hence, 2,487 children aged 6 to 12 years old were included in the DC group (935 males, 552 females; mean age6SD: 9.7561.88 years (95% CI = 9.68-9.82)), and 4,772 adolescents and young adults aged 13 to 20 years old were included in the DA group (2,920 males, 1,852 females; mean age6SD: 15.8561.92 years (95% CI = 15.79-15.90)). Medical grounds for special schooling were categorized into 8 groups as follows: 1) any intellectual disability, regardless of severity (45.4%);

Table 3 .

 3 Conditions observed by algorithms ranking children among Clinical Oral Care Needs Index values.

Table 4 .

 4 Conditions observed by algorithms ranking children among Clinical Oral Prevention Index values.

	COPI Values	CRITERIA
	1	Existence of systemic disease requiring specific oral health monitoring*
	Existence of at least one preventive or	or Presence of dental plaque
	dental health education action need
		or Lack of autonomy for feeding
		or Being fed by tube or parenteral nutrition
		or Restriction to pure ´ed foods
		or Eating hyper-calorific food complements or drinking sweetened drinks
		or Coughing regularly during meals
		or Presence of halitosis
		or Having difficulties communicating pain
		or Drooling
		or Being uncooperative during oral examination [38]
	0
	No need for either preventive health	Other conditions, by elimination
	action or dental education

*

as defined in the descriptive results section. doi:10.1371/journal.pone.0002564.t004

Table 7 .

 7 Distribution of children and adolescents with disabilities (respectively DC and DA groups) across the values of the Clinical Oral Health Index (COHI), the Clinical Oral Care Needs Index (COCNI) and the Clinical Oral Prevention Index (COPI) dependant on the training of the examiners.

		DC GROUP				DA GROUP
	Clinical Oral Health	Trained Examiners	Untrained examiners	Chi Square	Trained Examiners	Untrained examiners	Chi Square
	Index	(n = 269)		(n = 69)			(n = 269)		(n = 69)
	0: no problem	131	6.26%	26	6.58%	p = 0.35	64	1.67%	24	2.53%	p,0.05
	1: at least one low to	777	37.14%	164	41.52%		1594	41.68%	390	41.14%
	moderate problem
	2: at least one important	1043	49.86%	175	44.30%		1852	48.43%	430	45.36%
	to severe problem
	Unspecified level	141	6.74%	30	7.59%		314	8.21%	104	10.97%
	Total	2092	100%	395	100%		3824	100%	948	100%
	Clinical Oral Care	Trained Examiners	Untrained examiners	Chi Square	Trained Examiners	Untrained examiners	Chi Square
	Needs Index	(n = 269)		(n = 69)			(n = 269)		(n = 69)
	0: No need for care nor	199	9.51.%	45	11.39%	p = 0.10	292	7.64%	98	10.34%	p,0.01
	examination
	1: Need for examination	670	32.039%	117	29.62%		882	23.06%	241	25.42%
	2: Need for care	836	39.96%	177	44.81%		1945	50.86%	468	49.37%
	3: Urgent need for care	387	18.50%	56	14.18%		705	18.44%	141	14.87%
	or examination
	Total	2092	100%	395	100%		3824	100%	948	100%
	Clinical Oral	Trained Examiners	Untrained examiners	Chi Square	Trained Examiners	Untrained examiners	Chi Square
	Prevention Index	(n = 269)		(n = 69)			(n = 269)		(n = 69)
	0: No need for prevention	1231	58.84%	228	57.72%	p = 0.85	1853	48.46%	444	46.84%	p = 0.45
	or dental education
	1: Need for prevention or	861	41.16%	167	42.28%		1971	51.54%	504	53.16%
	dental education
	Total	2092	100%	395	100%		3824	100%	948	100%
	Chi square test compared the subjects' distribution between subgroups.
	doi:10.1371/journal.pone.0002564.t007

PLoS ONE | www.plosone.org

June 2008 | Volume 3 | Issue 6 | e2564

The survey that provided the data for the DC and DA groups was given financial support by three French national health insurance schemes (the Caisse Nationale d'Assurance Maladie des Travailleurs Salarie ´s (CNAMTS), the Mutualite ´Sociale Agricole (MSA) and the Assurance Maladie des Professions Inde ´pendantes (RSI)) that had pooled their resources under a national research program (Programme National Inter Re ´gimes 2004). The survey that provided the data for the NDC group was given financial support through two research teams: JE 2432 from the Auvergne region teacher training institute and EA 3847 from the University of Auvergne. The current analysis received financial support from the EA 3847 research team, which participated in building the methodology for both projects, designed the study, built the database, analyzed the data, wrote the paper, and managed the submission process for publication.

Author Contributions