Sarah Tigrine

Nathalie Carrasco

Ludovic Vettier

Olivia Chitarra

Guy Cernogora

Guy Cernogora The

The APSIS EXPERIMENT: Simulating the VUV Photochemistry of the Upper Atmosphere of Titan

published or not. The documents may come   L'archive ouverte pluridisciplinaire

The APSIS EXPERIMENT: Simulating the VUV Photochemistry of the Upper Atmosphere of Titan S. Tigrine 1, 2 , N. Carrasco 1 , L. Vettier 1 , O. Chitarra 1 , G. Cernogora 1 Titan, the largest moon of Saturn, has a dense atmosphere whose upper layers are mainly composed of methane (CH 4 ) and molecular nitrogen (N 2 ). The Cassini mission revealed that the interaction between those molecules and the solar VUV radiation, as well as the electrons from Saturn's magnetosphere, leads to a complex chemistry above an altitude of 800km [START_REF] Waite | The process of tholin formation in Titan's upper atmosphere[END_REF].

This naturally ionized environment contains heavy organic molecules like benzene (C 6 H 6 ) even at altitudes higher than 900 km [START_REF] Cravens | Composition of Titan's ionosphere[END_REF]. This is consistent with an initiation of the aerosols in Titan's upper atmosphere. Moreover, some N-bearing molecules of pre-biotic interest such as NH 3 have been detected by the instruments; but in quantities that do not match the theoretical models [START_REF] Krasnopolsky | A photochemical model of Titan's atmosphere and ionosphere[END_REF] .

 High interest of Titan's ionospheric chemistry experiments with pure-photochemistry simulations The photon flux of the source depends on the neon pressure and the micro-wave power delivered. We calculated it for the 73.5-nm neon line: it varies between a maximum of 4×10 14 ph.s -1 .cm-² (1.7 mbar and 100W) and a minimum of 2×10 13 ph.s -1 .cm-² (0.4 mbar and 40W) (figure 6).

The VUV Source

In order to reproduce the efficient photochemistry occurring in this kind of upper atmospheres, we designed a gas reactor named APSIS. This reactor is to be coupled with a VUV photon source (figure 5) as N 2 needs wavelengths shorter than 100 nm in order to be dissociated. The APSIS reactor is described in details in [START_REF] Carrasco | VUV photochemistry simulation of planetary upper atmosphere using synchrotron radiation[END_REF]. Briefly, it is a stainless steel chamber of dimensions 500 mm x 114 mm x 92 mm where the reactive 95:5 N 2 :CH 4 mixture is introduced via a gas inlet (figure 4)

The presence of those molecules makes Titan a natural laboratory to witness and understand prebiotic-like chemistry but despite all the data collected, all the possible chemical processes in such a hydrocarbon-nitrogen-rich environment are not precisely understood.

RESULTS

Figure 4: Scheme of the photochemical reactor coupled window-less with the VUV source.

References:

P APSIS = 0.5 mbar P neon = 1 mbar P w =80W Diagnosis by mass spectrometry: HIDEN HPR-20 QIC mass spectrometer

PERSPECTIVES

The high flexibility of our VUV source will allow us to change the rare gas and thus the wavelength used to irradiate the reactive mixture. For example, helium provides 58-nm radiations and argon 104-nm ones.

Inside APSIS, the pressures can also vary as well as the CH 4 ratio. Testing all those conditions will give us more information on the photochemical processes occuring in Titan's upper atmosphere and shed some light on prebiotic-like chemistry.

Figure 1 Figure 3 :

 13 Figure 1 & 2: Titan seen by the Cassini's imager

Figure 6 :Figure 5 :

 65 Figure 6: Photon flux of the VUV source versus the neon pressure and the microwave power

Figure 7 (

 7 Figure 7 (top): analogue mass spectra before (black curve) and after (red curve) irradiation with the VUV source Figure 8 (bottom): CH4 consumption monitored with time. The red lines show the moments the VUV source is turned ON.

Figure 9 (Figure 7

 97 Figure 9 (top): time-monitored productions of HCN (m/z=27) showing reproductibility. The red lines show the moments the VUV source is turned ON.Figure 10 (bottom): Same but for C2N2 (m/z=52)


S Tigrine
email: sarah.tigrine@latmos.ipsl.fr

N Carrasco

L Vettier

G Cernogora

A Micro----Wave Plasma Discharge in Rare Gases as a VUV Source for Planetary Atmospheric Photochemistry

The aim of this work is to show that micro-wave discharges in rare gases, can be an efficient windowless VUV photon source for planetary atmospheric photochemistry experiments. In this context, we perform a microwave discharge (surfatron) in a neon gas flow. We characterize the VUV photon flux emitted in different conditions, when working in the mbar pressure range, and compare it to synchrotron VUV fluxes also used for similar applications.

Experimental Setup

Neon plasma discharge: 40-cm length quartz tube, 8mm I.D. surrounded by a microwave surfatron resonance cavity designed for 2.45GHz. Gas flow: from 1 to 10 sccm, Pressure: measured upstream with a capacitor gauge, from 0.4 to 1.7 mbar.

Monochromator: Mac Pherson NOVA 225 VUV 1-m focal-length

The microwave plasma discharge is placed without window in front of its entrance slit and the gas is pumped by the monochromator pumping unit, The neon resonance lines at 73.59 and 74.37 nm [START_REF]NISTDatabase[END_REF] are studied

Results

Application: Atmospheric Photochemistry

The photon flux is calculated taking into account -the slits surfaces: 75µm width x 4 mm height; -as Ne is injected in the monochromator, the absorption is calculated along the 2m optical path using the Beer Lambert law and the Ne absorption cross section σ=9ൈ10 -17 cm² at 75 nm [START_REF] Hébrard | [END_REF] ; -the grating efficiency 6% at 75 nm ; -the Optodiode AXUV 100 detector efficiency 0.22 A W -1 at 75 nm ; -and the amplifier gain 1V for 1 nA .

ܫ 73.6݊݉ ∝ ݊ ܰ݁ ݇ ܶ ߥ ܫ 74.3 ݊݉ ∝ ݊ ܰ݁ ݇ ܶ ߥ ݇ ொ ܰ݁

Conclusion

The surfatron based low-pressure micro-wave discharge is an efficient tool as a VUV windowless source for planetary atmospheric photochemistry. The photon flux can be tuned by changing the working conditions (pressure and microwave power) of the discharge.

Fig, 5

The APSIS reactor designed for planetary atmospheric studies [3] (APSIS :Atmospheric Photochemistry SImulated by Synchrotron).

The VUV photon flux emitted at 73.6 nm can be tuned from 2×10 13 ph.s -1 .cm -2 to 4×10 14 ph.s -1 .cm -2 by changing the pressure conditions, These photons flux can be compared with the VUV DESIRS beamline of the synchrotron SOLEIL: at 17 eV (~75 nm) and for a resolving power of 1000, the VUV photon flux can be tuned from 7ൈ10 12 ph.s -1 .cm -² (for a 4mm×8mm spot) to 10 16 ph.s -1 .cm -² (for a 200 µm×100µm spot) [4].

First results for photochemistry

The simulation of Titan's atmosphere with a N 2 -CH 4 mixture (95% -5%)

73.6 nm line intensity can be described by a collisional radiative model

The limitation of the 74.3 nm line intensity is attributed to a quenching effect Fig. 2 The recorded Ne resonance lines Fig. 1: the surfatron discharge in front of the VUV monochromator

Fig. 3 Fig. 4

 34 Fig. 3 Photon flux emitted at 73,6 nm in different conditions of power versus the pressure. At high powers (P w >70W) and high pressures (P >1.5 mbar) amplifier saturates,

Fig. 6

 6 Fig. 6 Time-monitored mass spectrum -top: consumption of the reactive CH 4 -bottom: production of HCN (27) and C 2 N 2 ( 52)The red dotted lines mark the beginning of the irradiation of the reactor with the Ne discharge VUV source

Acknowledgments

S. Tigrine thanks the IDEX Paris Saclay for her Phd thesis grant N. Carrasco thanks the ERC Starting Grant PRIMCHEM, grant agreement n°636829. The Centre National d'Etudes Spatiales (CNES) supported the design of the APSIS reactor. All the authors also wish to thank L. Nahon for his kind support and advices.


Ajit A Diwan

Justine E Dion

David J Mendell

Michael J Plantholt

Shailesh K Tipnis
email: tipnis@ilstu.edu

The complexity of P 4-decomposition of regular graphs and multigraphs

Keywords: P4-decomposition, multigraphs, NP-complete

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

For integers i and j with i ≤ j, let [i, j] denote the set {i, i + 1, . . . , j}. A graph has no multiple edges or loops while a multigraph is allowed to have multiple edges but has no loops. Let G be a multigraph with vertex set V (G) and edge set E(G). The multiplicity of an edge (u, v) ∈ E(G) is defined to be the number of edges joining u and v and is denoted by µ(uv, G) and the maximum edge-multiplicity of G is denoted by µ(G). We denote by λ G the multigraph obtained from G by replacing each edge of G by λ parallel edges. A path consisting of 3 edges (x, y), (y, z),and (z, w) is denoted by P 4 and the edge (y, z) is called the central edge of P 4 . A decomposition of a multigraph G is a partition of its edge set into edge disjoint subgraphs H 1 , H 2 , . . . , H k of G; if each H i , i ∈ [1, k] is isomorphic to a graph H then we have an H-decomposition of G and we say that H decomposes G. It is well known that every connected multigraph G with the degree of each of its vertices being even has an Euler tour; we say that such a multigraph is Eulerian. We will denote an Euler tour in G by the sequence of vertices visited by the tour. An Euler tour in a multigraph G is said to be a triangle-free Euler tour if no three consecutive edges in the Euler tour form a triangle in G. A (C 2 , C 3 )-free Euler tour in a multigraph G is a triangle-free Euler tour in which no two consecutive edges are a parallel pair in G. We refer the reader to [START_REF] Bondy | Graph Theory[END_REF] for all terminology and notation that is not defined in this paper. The following conjecture by Graham and Häggkvist [START_REF] Häggkvist | Decompositions of complete bipartite graphs[END_REF] is the genesis of much of what we discuss in this paper.

Conjecture 1 [START_REF] Häggkvist | Decompositions of complete bipartite graphs[END_REF] Every tree on m edges decomposes every 2m-regular graph.

In [START_REF] Häggkvist | Decompositions of complete bipartite graphs[END_REF] Häggkvist described a method to prove the above conjecture for m = 3, i.e. that P 4 decomposes every 6-regular graph. M. Kouider and Z. Lonc [START_REF] Kouider | Path decompositions and perfect path double covers[END_REF] obtained a generalization of this result by showing that any path on m edges decomposes every 2m-regular graph G of girth g with m ≤ 2g -3.

The following theorem independently due to Kotzig [START_REF] Kotzig | Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades[END_REF] and Bouchet and Fouquet [START_REF] Bouchet | Trois types de decompositions d'un graphe en chaines[END_REF] gives a necessary and sufficient condition for a cubic graph to have a P 4 -decomposition.

Theorem 1 [START_REF] Bouchet | Trois types de decompositions d'un graphe en chaines[END_REF] A cubic graph G has a P 4 -decomposition if and only if G has a 1-factor.

Heinrich et al. [START_REF] Heinrich | P 4 -decompositions of regular graphs[END_REF] proved the following theorem as a corollary of a theorem on triangle-free Euler tours in connected 4-regular graphs.

Theorem 2 [START_REF] Heinrich | P 4 -decompositions of regular graphs[END_REF] A connected 4-regular graph G has a P 4 -decomposition if and only if |E(G)| is divisible by 3.

In Section 2 of this paper we extend Theorem 2 by proving that a connected 4-regular multigraph G with µ(G) ≤ 2 has a P 4 -decomposition if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Bondy [START_REF] Bondy | Perfect path double covers of graphs[END_REF] proved that if we double the edges of a cubic graph then P 4 decomposes the resulting multigraph.

Theorem 3 [START_REF] Bondy | Perfect path double covers of graphs[END_REF] Let G be a cubic graph. Then 2 G has a P 4 -decomposition.

The following generalization of Theorem 3 was obtained in [START_REF] El-Zanati | On decomposing even regular multigraphs into small isomorphic trees[END_REF].

Theorem 4 [START_REF] El-Zanati | On decomposing even regular multigraphs into small isomorphic trees[END_REF] Every 6-regular multigraph with µ(G) ≤ 2 has a P 4 -decomposition.

Theorem 4 was further generalized to multigraphs with higher multiplicity in [START_REF] El-Zanati | On decomposing even regular multigraphs into small isomorphic trees[END_REF].

Theorem 5 [START_REF] El-Zanati | On decomposing even regular multigraphs into small isomorphic trees[END_REF] For all integers k ≥ 1, every 6k-regular multigraph G with µ(G) ≤ 2k has a P 4decomposition.

In section 3 of this paper we prove the NP-Completeness of some P 4 -decomposition problems. Dor and Tarsi [START_REF] Dor | Graph decomposition is np-complete: A complete proof of holyer's conjecture[END_REF] proved the following classic NP-Completeness theorem about decompositions of graphs Theorem 7 [START_REF] Bryś | Polynomial cases of graph decomposition: A complete solution of holyer's problem[END_REF] For a fixed graph H with each component having at most 2 edges, the problem of determining if there exists an H-decomposition of an arbitrary graph G can be solved in polynomial time.

Theorem 6 implies that the problem of determining if P 4 decomposes an arbitrary graph G is NP-Complete. Teypaz and Rapine [START_REF] Teypaz | Graph decomposition into paths under length constraints[END_REF] proved that this remains true even under the restricted case where G is bipartite.

Theorem 8 [START_REF] Teypaz | Graph decomposition into paths under length constraints[END_REF] The problem of determining if there exists a P 4 -decomposition of an arbitrary bipartite graph G is NP-Complete.

Oksimets [START_REF] Oksimets | A characterization of Eulerian graphs with trianglefree Euler tours[END_REF] obtained the following theorem as a corollary of a result on triangle-free Euler tours in even-regular graphs.

Theorem 9 [START_REF] Oksimets | A characterization of Eulerian graphs with trianglefree Euler tours[END_REF] For all integers k ≥ 3, every connected 2k-regular graph G with |E(G)| being divisible by 3 has a P 4 -decomposition.

In section 3 of this paper we use a construction similar to the one used in the proof of Theorem 8 to prove that for all integers k ≥ 2, the problem of determining if P 4 decomposes a (2k + 1)-regular graph is NP-Complete. We also prove that for all integers k ≥ 3, the problem of determining if P 4 decomposes a 2k-regular multigraph G with µ(G) ≤ 2k 3 + 1 is NP-Complete. This shows that with respect to the maximum multiplicity of the multigraph, unless P = NP, Theorems 4 and 5 are best possible. In particular, in contrast to Theorem 4, this shows that the problem of determining if P 4 decomposes a 6-regular multigraph with maximum multiplicity 3 is NP-Complete.

P 4 -decomposition of 4-regular multigraphs of maximum multiplicity 2

A (2,4)-multigraph is a multigraph whose vertices have degree 2 or 4. Let G be the family of connected (2,4)-graphs shown in Figure 1 where H is any graph with appropriate degrees. Heinrich et al. [START_REF] Heinrich | P 4 -decompositions of regular graphs[END_REF] proved that the graphs in G are the only connected (2,4)-graphs that do not admit a triangle-free Euler tour. We now prove extensions of these results by Heinrich et al. [START_REF] Heinrich | P 4 -decompositions of regular graphs[END_REF] to multigraphs G with µ(G) ≤ 2. Let F be the family of connected (2,4)-multigraphs shown in Figure 2 where H is any multigraph with appropriate degrees. Let u and v be adjacent vertices of G with µ(u, v) = 2, and let G * be the graph obtained from G by subdividing one of the edges (u, v) by inserting a new vertex w. Clearly, G * is a connected (2,4)multigraph with p(G * ) = k. We claim that G * ∈ F. If G * ∈ F then the inserted vertex w of degree two must be a depicted vertex of one of the multigraphs in Figure 2. But note that the multigraph obtained by deleting any depicted vertex x of degree two from any of the multigraphs in Figure 2 and joining the neighbors of x by an edge results in a multigraph in F or an edge of multiplicity three or a loop. For example, performing this operation on the multigraph XIII in Figure 2 results in multigraph X. Hence, since G ∈ F, we have that G * ∈ F as claimed.

By the induction hypothesis we have that G * has (C 2 , C 3 )-free Euler tour E * and we may assume without loss of generality that u, w, v is a subsequence of E * . Let E be the Euler tour of G obtained from E * by replacing its subsequence u, w, v by u, v. Since E * is (C 2 , C 3 )-free, E is C 2 -free and we are done if in addition E is C 3 -free. So, assume that some 3 consecutive vertices in E form a triangle in G which must clearly contain the edge (u, v) and hence we can assume that E starts with the subsequence u, v, t, u for some vertex t = u, v. Because E is C 2 -free, it cannot end with the subsequence v, u, and hence we can further assume that E starts with the subsequence u, v, t, u, v. But then, E * must contain either the subsequence u, w, v, t, u, v or u, v, t, u, w, v. In either case, this implies that E * contains a C 3 -subsequence which is a contradiction. The result follows.

2

Theorem 11 directly yields the corollary below by appropriately segmenting a (C 2 , C 3 )-free Euler tour into 3-edge segments.

Corollary 1 Let G be a connected (2,4)-multigraph with µ(G) ≤ 2. If G ∈ F and |E(G)| is divisible by 3 then G admits a P 4 decomposition.
We are now ready to prove the main result of this section. Let G be a connected 4-regular multigraph with µ(G) ≤ 2, with |E(G)| divisible by 3, and such that no three vertices of G induce more than 4 edges. If G ∈ F, the result follows from Corollary 1. So assume G ∈ F. Clearly, G must be a type IX, X, or XIV graph (and perhaps, all three) in F.

We will construct from G a connected (2,4)-multigraph G * ∈ F and with |E(G * )| divisible by 3. Theorem 11 will then imply that G * admits a (C 2 , C 3 )-free Euler tour, and hence a P 4 decomposition. We will then show how this P 4 decomposition of G * yields a P 4 decomposition of G.

We construct G * by replacing the subgraph induced by the 4 vertices shown in Figure 2 in type IX or type X structures in G by paths of length 4, and, the subgraph induced by the 5 vertices shown in Figure 2 in type XIV structures in G by paths of length 3. Note that the lengths of these paths mod 3 is equal to the number of edges mod 3 in the induced subgraphs that they replace.

Clearly, G * ∈ F is a connected (2,4)-multigraph with µ(G * ) ≤ 2, and |E(G * )| divisible by 3, and hence by Theorem 11 has a (C 2 , C 3 )-free Euler tour, T * . We now use T * to construct an Euler tour, T , in G which will provide a P 4 -decomposition of G.

Begin by traversing T * until the next vertex to be reached is contained in a replacement path. Let m be the number of edges traversed until now reduced modulo 3. Remove the replacement path added in the construction of G * , and reinstate the original induced subgraph on 4 or 5 vertices that was replaced by it. In Figures 3,4, and 5, the directions in which these edges should be traversed are indicated with arrows, and the order in which the edges are to be traversed have been indicated by labels that occur in sets of three, which also indicate which edges will be partitioned together in the final P 4 -decomposition of G. Note that we lose no generality by assuming that the reinstated subgraph is entered from the left-hand side in Figures 3, 4, and5. Even in the case of a type IX graph in F, which is not strictly symmetric, it is easy to confirm a symmetry between the labelings given in Figures 3(a 3 NP-Completeness of some regular graph/multigraph decomposition problems

For an integer m ≥ 3, X3C(m) is the following exact 3-cover problem.

X3C(m)

Given: A finite ground set X and a collection of subsets S = {S i } k i=1 of X with |S i | = 3 for each i ∈ [1, k] and each element of X contained in exactly m sets in S. Question: Is there a subcollection Q ⊆ S such that each element of X is contained in exactly one set in Q? If for some instance I of X3C(m), the subcollection Q in the above question exists, we say that I has an exact cover consisting of Q. Gonzalez [START_REF] Teofilo | Clustering to minimize the maximum intercluster distance[END_REF] proved that Exact 3-cover is NP-complete if each element of the ground set is contained in exactly 3 subsets.

Theorem 13 [7] X3C(3) is NP-complete.
We first prove the following more general form of Theorem 13.

Theorem 14 For every integer m ≥ 3, X3C(m) is NP-complete.

Proof: Clearly, the problem is in NP. Theorem 13 verifies the case m = 3. Suppose we have an instance I of X3C(n) with ground set X and a collection of subsets S of X, for some integer n ≥ 3. We will construct an instance I' of X3C(n + 1) with ground set X and a collection of subsets S of X such that I has an exact cover if and only if I' has an exact cover.

Without loss of generality suppose that |X| = 3q, otherwise trivially, no exact cover exists for instance I. Partition the elements in X arbitrarily into q sets X s = {x

(s) 1 , x (s) 2 , x (s) 3 }, for each s ∈ [1, q]. Let X = X ( q s=1 {a (s) 1 , a (s) 2 , . . . , a (s) 3(n+1) }), where a (s) i is a new element not contained in X for each i ∈ [1, 3(n + 1)] and s ∈ [1, q].
The collection of subsets S of X is better described by first constructing a collection of subsets S and then amending S to get S . Let S = S (

q s=1 {{a (s) 3i+1 , a (s) 3i+2 , a (s) 3j+3 } : 0 ≤ i, j ≤ n}). Note that for each i ∈ [1, 3(n + 1)] and s ∈ [1, q], a (s) i
is contained in exactly (n + 1) subsets of S . Now, to construct the collection of subsets S we amend S as follows: Delete the 3q sets {a

(s) 3n+1 , a (s) 3n+2 , a (s)
3j+3 } for each 0 ≤ j < 3 and each s ∈ [1, q], add the sets {a for each s ∈ [1, q] are contained in (n + 1) sets and these are contained in exactly (n -2) sets. Finally, add the sets {x

(s) i , a (s) 3n+2 , a (s)
3n+3 } for each i ∈ [1, 3] and each s ∈ [1, q]. We now have the collection of subsets S of X of cardinality 3 each and such that each element of X is contained in exactly (n + 1) sets in S . Now if I has an exact cover

Q then Q = Q ( q s=1 {{a (s) 3i+1 , a (s) 3i+2 , a (s) 3i+3 } : i ∈ [0, n]}) is an exact cover for I'. Conversely, if Q is an exact cover of I', then no set of the form {x (s) i , a (s) 3n+2 , a (s) 3n+3 } for i ∈ [1, 3] and s ∈ [1, q] can be Q , since if so, it is impossible to cover the elements a (s) i for i ∈ [1, 3(n + 1)] \ {3n + 2, 3(n + 1)} and s ∈ [1, q].
Hence, in I', the elements of the ground set X of I must be covered by sets in S which gives an exact cover for I.

2

We now use Theorem 13 to prove that the problem of determining if P 4 decomposes a 5-regular graph is NP-complete, and point out that Theorem 14 can be used to prove more generally that for all integers k ≥ 2, the problem of determining if P 4 decomposes a (2k + 1)-regular graph is NP-complete.

Theorem 15 Given a 5-regular graph G, the problem of determining if P 4 decomposes G is NP-Complete.

Proof: Clearly the problem is in NP. We will prove the theorem by reduction from the NP-Complete problem X3C(3). Consider an arbitrary instance I of X3C(3) with ground set X and a collection of subsets S = {S i } k i=1 of X with |S i | = 3 for each i ∈ [1, k] and each element of X contained in exactly 3 sets in S. Without loss of generality assume that |X| = |S| = 3q and let X = {x 1 , x 2 , . . . , x 3q }. We will construct a 5-regular graph G such that P 4 decomposes G if and only if I has an exact cover. For each element x i ∈ X, we have a vertex

v i ∈ V (G), i ∈ [1, 3q]. For each set S i ∈ S, we will construct a set-gadget graph G i , i ∈ [1, 3q]. If S i = {x j , x k , x l } then G i has 3 vertices w (i) j , w (i)
k , and w (i) l of degree 4 each and 6 vertices a i , b i , c i , d i , e i , and f i of degree 5 each, so that |E(G i )| = 21 = 0 (mod 3). In addition we choose G i and G i \ T to be P 4 -decomposable, where T is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree 4. Figure 6 shows an example of G i with these properties. The letters by the edges indicate a P 4 -decomposition of the gadget. Also note that if you remove the edges (w i j , d i ), (d i , b i ), (w i k , f i ), (f i , d i ), (w i l , a i ), and (a i , d i ) the letters on the edges continue to indicate a P 4 -decomposition of the remaining edges such that H (j) i -e is P 4 decomposable, where e is an edge incident on the vertex of degree 4. Figure 7 shows an example of H 1 i with these properties. The letters to the right or above the edges indicate a P 4 -decomposition of the gadget with the exception of one edge incident on the vertex of degree 4. In G, for each i ∈ [1, 3q], vertex v i is joined by an edge to vertices u (1) i and u

w i l a i d i b i c i f i e i w i j w i k G B G D F G B E E E A C D D F C C A B F A Fig. 6: Set gadget graph G i for set S i = {x j , x k , x l } In G, if x i ∈ S j , vertex v i is joined to vertices w (j) i , for each i, j ∈ [1, 3q]. For each element x i ∈ X, we construct two disjoint copies H (1) i , H (2)
(2) i . This completes the construction of the graph G.

Suppose that the instance I of X3C(3) has an exact cover Q.

If for i ∈ [1, 3q] set S i = {x j , x k , x l } ∈ Q, we use 3 edge-disjoint paths of length 2 in G i starting at w (i) j , w (i) k and w (i) l
together with the edges

v j w (i) j , v k w (i) k and v l w (i)
l that are external to G i as 3 P 4 s in a decomposition of G. The rest of the 15 edges in G i decompose internally into P 4 s. For S i ∈ Q we decompose all the 21 edges in G i internally into P 4 s. Since Q is an exact cover of I, for each i ∈ [1, 3q], this leaves uncovered exactly 2 edges joining v i to vertices corresponding to 2 sets in S \ Q. We use these 2 uncovered edges together with the edges v i u Conversely suppose that G has a P 4 -decomposition. For i ∈ [1, 3q], the P 4 s that are internal to H

(1) i and H

(2) i in the decomposition leave exactly one internal edge uncovered incident on each of u (1) i and u

(2) i . In any P 4 -decomposition of G these uncovered edges must be covered by P 4 s that include the

u 1 i C A B B A A D B F C D F D G G F E E G E C Fig. 7: Element gadget H 1 i for element x i edges u (1)
i v i and u

i v i together with 2 edges joining v i to corresponding vertices w

for some j, k ∈ [1, 3q]. For each i ∈ [1, 3q], this leaves exactly one edge incident on v i uncovered that joins v i to a corresponding vertex w (l) i for some l ∈ [1, 3q].

For each i ∈ [1, 3q], let X i = {v j w (i) j , v k w (i) k , v l w (i)
l } be the set of edges that have exactly one endpoint in V (G i ). We claim that in any P 4 -decomposition of G, for each i ∈ [1, 3q] the P 4 s that cover the edges in G i include all three or none of the edges in X i . To see this, note that if exactly one of the edges in X i is included in the P 4 s that cover the edges in G i , then that edge must be in a P 4 that includes 2 edges in E(G i ) and that leaves the remaining 19 edges in E(G i ) to be covered internally, which is impossible. If exactly two of the edges in X i are included in the P 4 s that cover the edges in G i , then, clearly, this leaves either 17 or 20 edges in E(G i ) to be covered internally, which is impossible. Now, it is easy to see that the sets corresponding to those set-gadget graphs G i , i ∈ [1, 3q], for which the P 4 s that cover the edges in G i include all three edges in X i form an exact cover of I.

2

We point out that by using the more general Theorem 14, a proof similar to that of Theorem 15 yields the NP-Completeness of the problem of determining if a (2k + 1)-regular graph has a P 4 -decomposition for all k ≥ 2.

Theorem 16 For all k ≥ 2, given a (2k + 1)-regular graph G, the problem of determining if P 4 decomposes G is NP-Complete.

Proof: Clearly the problem is in NP. Theorem 14 gives that X3C(k +1) is NP-Complete for all k ≥ 2. We prove the theorem by reduction from X3C(k + 1) for k ≥ 2. Given an arbitrary instance I of X3C(k + 1) for k ≥ 2, we will only describe the set-gadget graphs, the element-gadget graphs, and the graph G which is (2k + 1)-regular and such that I has an exact cover if and only if P 4 decomposes G. As in the proof of Theorem 15 we have a set-gadget graph for each subset of the ground set. The set-gadget graph G i has 3 vertices of degree 2k each, all other vertices of G i have degree (2k + 1) each, |E(G i )| = 0 (mod 3), G i is P 4 decomposable, and G i \ T is decomposable where T is a set of 6 edges consisting of edge-disjoint paths of length 2 starting at each of the 3 vertices of degree 2k. Corresponding to each element x i of the ground set we have a vertex v i and k copies of an element gadget graph H e is P 4 decomposable, where e is an edge incident on the vertex of degree 2k. For each element x i in the ground set, the corresponding vertex v i is joined to the k vertices of degree 2k in each of the associated element-gadget graphs H (j) i , j ∈ [1, k], and v i is joined to one of the 3 vertices of degree 2k in each of the associated set-gadget graphs that correspond to the (k + 1) subsets that contain x i . Now, an argument similar to that in the proof of Theorem 15 shows that I has an exact cover if and only if P 4 decomposes G.

2

We will now use Theorem 16 to prove the NP-Completeness of the problem of determining if P 4 decomposes certain regular multigraphs.

Theorem 17 For all integers k ≥ 1, the problem of determining if P 4 decomposes a 6k-regular multigraph G with µ(G) ≤ (2k + 1) is NP-Complete.

Proof: Clearly, the problem is in NP. Theorem 16 gives that the problem of determining if P 4 decomposes a (6k -1)-regular graph is NP-Complete for all integers k ≥ 1. We will prove our theorem by reduction from this NP-Complete problem.

For k ≥ 1, given a (6k -1)-regular graph G, we will construct a 6k-regular multigraph G with µ(G ) ≤ (2k + 1) such that P 4 decomposes G if and only if P 4 decomposes G . If |V (G)| = n, we will use n copies of the following gadget graph H in our construction of G . To construct the gadget H, take 3 disjoint cliques Q 1 , Q 2 , and Q 3 on 2k vertices each and remove a perfect matching from Q 1 and Q 2 . Add 2k disjoint triangles, each containing one vertex from each of the 3 cliques. The edges of these triangles joining a vertex in Q 1 to a vertex in Q 2 have multiplicity (2k + 1), and all other edges of these triangles have multiplicity 2k. This completes the construction of the gadget graph H which is (6k -1)-regular and has µ(H) ≤ (2k + 1). In the construction of G we will add one edge between each vertex of a copy of H and the rest of G . Now, given a (6k -1)-regular graph G on

n vertices v i , i ∈ [1, n], make 6k disjoint copies G i , i ∈ [1, 6k] of G, and n disjoint copies H i , i ∈ [1, n] of H. Join each vertex of H i to a different copy of v i ∈ 6k j=1 V (G j ) for i ∈ [1, n].
This completes the construction of the graph G . Suppose P 4 decomposes G. We decompose each G i , i ∈ [1, 6k] separately. It is easy to check that each H i , i ∈ [1, n] together with the 6k edges between a vertex of H i and a vertex not in V (H i ) can be decomposed into P 4 s separately. This yields a P 4 -decomposition of G .

Conversely, suppose P 4 decomposes G . We claim that the edges in each H i , i ∈ [1, n] together with the 6k edges between a vertex of H i and a vertex not in V (H i ) must be decomposed into P 4 s without using any other edges. To prove this claim note that the total number of edges contained in the 2k disjoint triangles added to the 3 cliques in H i is (2k)(6k + 1). Any P 4 can contain at most 2 edges from these triangles and hence in any decomposition of G there are at least (k)(6k + 1) = (6k 2 + k) P 4 's that contain edges from these triangles. In addition, any of these (6k 2 + k) P 4 's must use an edge from one of the cliques Q i , i ∈ [START_REF] Bondy | Perfect path double covers of graphs[END_REF][START_REF] Bouchet | Trois types de decompositions d'un graphe en chaines[END_REF] or an edge joining a clique vertex to the rest of the graph G . Since there are exactly (6k 2 + k) such edges, the claim follows. Now, the P 4 -decomposition of any G i , i ∈ [1, 6k] in the decomposition of G gives a P 4 -decomposition of G.

2

We now prove a strengthening of Theorem 17 above. In the construction of G we will add one edge between each vertex of a copy of H and the rest of G . Now, given a (6m + 1)-regular graph G on n vertices v i , i ∈ [1, n], make 6m disjoint copies G i , i ∈ [1, 6m] of G, and n disjoint copies H i , i ∈ [1, n] of H. Join each vertex of H i to a different copy of v i ∈ 6m j=1 V (G j ) for i ∈ [1, n]. This completes the construction of the graph G . Now, as in the proof of Theorem 17, we can argue that the edges in each H i , i ∈ [1, n] together with the 6m edges between a vertex of H i and a vertex not in V (H i ) must be decomposed into P 4 s without using any other edges. The rest of the proof is similar to that of Theorem 17. To complete the proof, suppose that k = 3m + 2 for some integer m ≥ 1. For m ≥ 1, given a (6m + 3)regular graph G, we will construct a (6m + 4)-regular multigraph G with µ(G ) ≤ (2m + 2) such that P 4 decomposes G if and only if P 4 decomposes G . This will prove the theorem for this case because by Theorem 16 the problem of determining if P 4 decomposes a (6m + 3)-regular graph is NP-Complete for all m ≥ 1. If |V (G)| = n, we will use n copies of the following gadget graph H in our construction of G . To construct the gadget H, take 3 disjoint copies Q 1 , Q 2 , and Q 3 of the clique K 2m and add 2m disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of the edges between a vertex of Q 1 and a vertex of Q 2 being (2m + 1) and the multiplicity of all other edges of the added triangles being (2m+2). Now, add a perfect matching with 2m edges between cliques Q 1 and Q 2 making sure that none of the edges in the matching are parallel to any edge of the triangles added earlier. This completes the construction of the gadget graph H which is (6m + 3)-regular and has µ(H) ≤ (2m + 2). In the construction of G we will add one edge between each vertex of a copy of H and the rest of G . Now, given a (6m + 3)-regular graph G on n vertices v i , i ∈ [1, n], make 6m disjoint copies G i , i ∈ [1, 6m] of G, and n disjoint copies H i , i ∈ [1, n] of H. Join each vertex of H i to a different copy of v i ∈ 6m j=1 V (G j ) for i ∈ [1, n]. This completes the construction of the graph G . The rest of the proof is similar to the proof of Theorem 17.

2

We note that the proof of Theorem 18 used gadgets for a 2k-regular multigraph G that contain triangles with (2k + 1) edges. In view of this we offer the following conjecture which is verified by Theorem 12 in the case when k = 2 and which implies Theorem 5 when k is a multiple of 3.

Theorem 10 [ 9 ]

 109 A connected (2,4)-graph G admits a triangle-free Euler tour if and only if G ∈ G.

Fig. 1 :

 1 Fig. 1: Family G of (2,4)-graphs with no triangle-free Euler tour.

Theorem 11 A

 11 connected (2,4)-multigraph G with µ(G) ≤ 2 admits a (C 2 , C 3 )-free Euler tour if and only if G ∈ F. Proof: If G ∈ F, it is easy to check that G does not admit a (C 2 , C 3 )-free Euler tour. Let G ∈ F be a connected (2,4)-multigraph with µ(G) ≤ 2 and let p(G) be the number of parallel edge pairs in G. We prove the theorem by induction on p(G). The base case p(G) = 0 follows from Theorem 10 because in that case G has no multiple edges and the family G of graphs in Figure 1 is contained in the family F in Figure 2. Suppose inductively that the theorem is true for 0 ≤ p(G) ≤ k. Let G ∈ F be a connected (2,4)-multigraph with µ(G) ≤ 2 and p(G) = k + 1.

Fig. 2 :

 2 Fig. 2: Family F of multigraphs with no (C 2 , C 3 )-free Euler tour.

Theorem 12 A

 12 connected 4-regular multigraph G with µ(G) ≤ 2 admits a P 4 decomposition if and only if no 3 vertices of G induce more than 4 edges and |E(G)| is divisible by 3. Proof: Clearly, if G has a P 4 -decomposition then |E(G)| is divisible by 3 and no three vertices of G induce more than 4 edges.

Fig. 3 :

 3 Fig. 3: Labelings for type IX subgraphs being reinstated.

Fig. 4 :

 4 Fig. 4: Labelings for type X subgraphs being reinstated.

Fig. 5 :

 5 Fig. 5: Labelings for type XIV subgraphs being reinstated.

  for each s ∈[1, q], and, replace the element a (s) 3n+3 in the sets {a 3n+3 } for 0 ≤ i < 3 by the element a (s) 3n+1 for each s ∈ [1, q]. Now all new elements except a (s) 3n+2 and a (s) 3n+3

  i of an element-gadget graph, i ∈ [1, 3q]. For j = 1 and 2, graph H (j) i has one vertex u (j) i of degree 4 and 8 vertices of degree 5, so that |E(H (j) i )| = 22 = 1 (mod 3). In addition, we choose H (j) i

as 2 P

 2 4 s in the decomposition of G. The remaining 21 edges in each of H internally into P 4 s for each i ∈ [1, 3q].

i

  , j ∈ [1, k]. Each elementgadget graph H (j) i has one vertex of degree 2k, all other vertices of H (j) i have degree (2k + 1) each, |E(H (j) i )| = 1 (mod 3), and H (j) i

  Theorem 18 For all integers k ≥ 3, the problem of determining if P 4 decomposes a 2k-regular multigraph G with µ(G) ≤ 2k 3 + 1 is NP-Complete. Proof: Clearly, the problem is in NP. If k is a multiple of 3 then the theorem follows from Theorem 17 above. So, suppose that k = 3m + 1 for some integer m ≥ 1. For m ≥ 1, given a (6m + 1)-regular graph G, we will construct a (6m + 2)-regular multigraph G with µ(G ) ≤ (2m + 1) such that P 4 decomposes G if and only if P 4 decomposes G . This will prove the theorem for this case because by Theorem 16 the problem of determining if P 4 decomposes a (6m + 1)-regular graph is NP-Complete for all m ≥ 1. If |V (G)| = n, we will use n copies of the following gadget graph H in our construction of G . To construct the gadget H, take 3 disjoint copies of the clique K 2m and add 2m disjoint triangles, each containing one vertex from each of the 3 cliques with the multiplicity of each edge of these triangles being (2m+1). This completes the construction of the gadget graph H which is (6m + 1)-regular and has µ(H) ≤ (2m + 1).

Acknowledgements

We would like to thank the anonymous referee for a careful reading of our paper and in particular for pointing out an error in our original proof of Theorem 11.

Conjecture 2 Let G be a connected 2k-regular multigraph G with µ(G) ≤ 2k 3 + 1 and such that any three vertices in G induce at most 2k edges. Then P 4 decomposes G if and only if |E(G)| is divisible by 3.


Matthias Kriesell
email: matthias.kriesell@tu-ilmenau.de

Anders Sune Pedersen

On graphs double-critical with respect to the colouring number

Keywords: graph colouring, graph characterizations, degenerate graphs, colouring number, double-critical graphs

The colouring number col(G) of a graph G is the smallest integer k for which there is an ordering of the vertices of G such that when removing the vertices of G in the specified order no vertex of degree more than k -1 in the remaining graph is removed at any step. An edge e of a graph G is said to be double-col-critical if the colouring number of G -V (e) is at most the colouring number of G minus 2. A connected graph G is said to be double-col-critical if each edge of G is double-col-critical. We characterise the double-col-critical graphs with colouring number at most 5. In addition, we prove that every 4-col-critical non-complete graph has at most half of its edges being double-col-critical, and that the extremal graphs are precisely the odd wheels on at least six vertices. We observe that for any integer k greater than 4 and any positive number , there is a k-col-critical graph with the ratio of double-col-critical edges between 1and 1.

Introduction

All graphs considered in this paper are assumed to be simple and finite. (i) The cycle on n vertices is denoted by C n . The complete graph K n on n vertices is referred to as an n-clique. Let G denote a graph. The number of vertices in a largest clique contained in G is denoted by ω(G). The vertex-connectivity of G is denoted by κ(G). The number of vertices and edges in G is denoted by n(G) and m(G), respectively. Given a vertex v in G, N (v, G) denotes the set of vertices in G adjacent to v; deg(v, G) denotes the cardinality of N (v, G), and it is referred to as the degree of v (in G). A vertex of degree 1 is referred to as a leaf. The minimum degree and maximum degree of G is denoted δ(G) and ∆(G), respectively. Given a subset S of the vertices of G, the subgraph of G induced by the vertices of S is denoted by G[S], and we let N (S, G) denote the set ∪ s∈S N (s, G) \ S. The square of a graph G, denoted by G 2 , is the graph obtained from G by adding edges between any pair of vertices of G which are at distance 2 in G. Given two graphs H and G, the complete join of G and H, denoted by G + H, is the graph obtained from two disjoint copies of H and G by joining each vertex of the copy of G to each vertex of the copy of H. The chromatic number of G is denoted by χ(G), while the list-chromatic number of G is denoted by χ (G). Let ψ denote some graph parameter. An edge e of G is said to be double-ψ-critical if ψ(G -V (e)) ≤ ψ(G) -2. A connected graph G is said to be double-ψ-critical if each edge of G is double-ψ-critical. For brevity, we may also refer to double-χ-critical edges and graphs as, simply, doublecritical edges and graphs, respectively.

The introduction of the concept of double-ψ-critical graphs in [START_REF] Pedersen | Contributions to the Theory of Colourings, Graph Minors, and Independent Sets[END_REF] was inspired by a special case of the Erdős-Lovász Tihany Conjecture [START_REF] Erdős | Problem 2. In Theory of Graphs[END_REF], namely the special case which states that the complete graphs are the only double-critical graphs. We refer to this special case of the Erdős-Lovász Tihany Conjecture as the Double-Critical Graph Conjecture. The Double-Critical Graph Conjecture is settled in the affirmative for the class of graphs with chromatic number at most 5, but remains unsettled for the class of graphs with chromatic number k, for each value of k ≥ 6. [START_REF] Jensen | Graph Coloring Problems[END_REF][START_REF] Mozhan | Twice critical graphs with chromatic number five[END_REF][START_REF] Stiebitz | K5 is the only double-critical 5-chromatic graph[END_REF][START_REF] Stiebitz | On k-critical n-chromatic graphs[END_REF]. Using the computer programs SAGE [START_REF] Stein | Sage Mathematics Software (Version 4.6.2)[END_REF] and geng [START_REF] Mckay | geng -a program for generating graphs[END_REF], we verified the Double-Critical Graph Conjecture for all graphs on at most 12 vertices (see [START_REF] Pedersen | [END_REF]).

In [START_REF] Pedersen | Contributions to the Theory of Colourings, Graph Minors, and Independent Sets[END_REF], it was proved that if G is a double-χ -critical graph with χ (G) ≤ 4, then G is complete. It is an open problem whether there is a non-complete double-χ -critical graph with list-chromatic number at least 5.

The double-κ-critical graphs, which in the literature are referred to as contraction-critical graphs (since the vertex-connectivity drops by one after contraction of any edge), are well-understood in the case where κ is 4. Some structural results have been obtained for contraction-critical graphs with vertex-connectivity 5. (See [START_REF] Kriesell | A survey on contractible edges in graphs of a prescribed vertex connectivity[END_REF]Sec. 4] for references on contraction-critical graphs.) Bjarne Toft (ii) posed the problem of characterising the double-col-critical graphs. Here col denotes the colouring number which is defined in the paragraph below.

In this paper, we characterise the double-col-critical graphs with colouring number at most 5.

In the remaining part of this section, we define the colouring number and present some fundamental properties of this graph parameter.

The colouring number of a graph. Suppose that we are given a non-empty graph G and an ordering v 1 , . . . , v n of the vertices of G. Now we may colour the vertices of G in the order v 1 , . . . , v n such that in the ith step the vertex v i is assigned the smallest possible positive integer which is not assigned to any neighbour of v i among v 1 , . . . , v i-1 . This produces a colouring of G using at most max i∈{1,...,n}

deg(v i , G[v 1 , . . . , v i ]) + 1
colours. Taking the minimum over the set S n of all permutations of {1, . . . , n}, we find that the chromatic number of G is at most

min π∈Sn max i∈{1,...,n} deg(v π(i) , G[v π(1) , . . . , v π(i) ]) + 1 (1)
The number in (1) is called the colouring number of G, and it is denoted by col(G). The colouring number of the empty graph K 0 is defined to be zero. By [START_REF] Bondy | Graph Theory[END_REF], col(G) ≤ ∆(G) + 1 for any graph G.

(ii) Private communication to the second author from Bjarne Toft, Odense, August 2008.

The colouring number was introduced by Erdős and Hajnal [START_REF] Erdős | On chromatic number of graphs and set-systems[END_REF], but equivalent concepts were introduced independently by several other authors. It can be shown (see, for instance, [START_REF] Toft | Colouring, stable sets and perfect graphs[END_REF]) that the colouring number of any non-empty graph G is equal to

max{δ(H) | H is an induced subgraph of G} + 1 (2)
and that the colouring number can be computed in polynomial time [START_REF] Matula | Smallest-last ordering and clustering and graph coloring algorithms[END_REF]. The non-empty graphs with colouring number at most k + 1 are also said to be k-degenerate [START_REF] Lick | k-degenerate graphs[END_REF]. Thus, a non-empty graph G is k-degenerate if and only if there is an ordering of the vertices of G such that when removing the vertices of G in the specified order no vertex of degree more than k in the remaining graph is removed at any step.

The colouring number is monotone on subgraphs, that is, if F is a subgraph of a graph G then col(F ) ≤ col(G). For ease of reference, we state the following elementary facts concerning the colouring number of graphs.

(iv) col(G) ≥ 3 if and only if G contains at least one cycle. A graph G is said to be k-col-critical, or, simply, col-critical, if col(G) = k and col(F ) < k for every proper subgraph F of G. Similarly, a graph G is said to be k-col-vertex-critical, or, simply, col-vertex- critical, if col(G) = k and col(F ) < k for every induced proper subgraph F of G.
It is easy to see that every connected r-regular graph is (r + 1)-col-critical.

Observation 2 For any col-vertex-critical graph G,

(i) col(G) = 0 if and only if G K 0 , (ii) col(G) = 1 if and only if G K 1 , (iii) col(G) = 2 if and only if G K 2 ,

and

(iv) col(G) = 3 if and only if G is a cycle.

Observation 3 For any graph G and any element

x ∈ E(G) ∪ V (G), if col(G -x) < col(G) then col(G -x) = col(G) -1. Observation 4 A graph G is col-vertex-critical if and only if col(G -v) < col(G) for every vertex v in G. Observation 5 Given any graph G, there is a col-critical subgraph F of G with col(G) = col(F ) = δ(F ) + 1. In particular, if G is col-critical then col(G) = δ(G) + 1. Proof: Recall that col(G) = max{δ(H) | H ⊆ G} + 1. Among the subgraphs H of G with col(G) = δ(H) + 1, let F denote a minimal one, that is, δ(F ) < δ(F ) for every proper subgraph F of F . (This minimum exists since G is finite.) Then F is col-critical with col(F ) = δ(F ) + 1 = col(G). 2 Observation 6 Given any graph G, there is a col-vertex-critical induced subgraph F of G with col(G) = col(F ) = δ(F ) + 1. In particular, if G is col-vertex-critical then col(G) = δ(G) + 1.
Proof: Let F denote a minimal induced subgraph of G with col(F ) = col(G). This implies col(F ) < col(F ) for any induced proper subgraph F of F , in particular, F is a col-vertex-critical graph. Suppose col(F ) > δ(F ) + 1. Then there is some proper induced subgraph F of F with δ(F ) + 1 = col(F ), and so col(F ) ≥ col(F ), a contradiction. Hence col(F ) = δ(F ) + 1. If G is col-vertex-critical, then F = G, and the desired result follows. 2

The two following results may be of interest in their own right.

Proposition 1 (Pedersen [START_REF] Pedersen | Contributions to the Theory of Colourings, Graph Minors, and Independent Sets[END_REF]) For any two non-empty disjoint graphs G 1 and G 2 , the colouring number of the complete join

G 1 + G 2 is at most min{col(G 1 ) + n(G 2 ), col(G 2 ) + n(G 1 )} (3)
and at least

min{col(G 1 ) + n(J 2 ), col(G 2 ) + n(J 1 )} (4)
where, for each i ∈ {1, 2}, J i is any subgraph of G i with minimum degree equal to col(G i ) -1.

If, in addition, col(G i ) = δ(G i ) + 1 for each i ∈ {1, 2} (in particular, if both G 1 and G 2 are colvertex-critical), then the colouring number of the complete join G 1 + G 2 is equal to the minimum in [START_REF] Erdős | On chromatic number of graphs and set-systems[END_REF].

A graph G is said to be decomposable if there is a partition of V (G) into two (non-empty) sets V 1 and V 2 such that, in G, every vertex of V 1 is adjacent to every vertex of V 2 . Given any graph G, we let V δ (G) denote the set of vertices of G of minimum degree in G. Clearly, V δ (G) is non-empty for any non-empty graph.

Proposition 2 (Pedersen [START_REF] Pedersen | Contributions to the Theory of Colourings, Graph Minors, and Independent Sets[END_REF]) Let G denote a decomposable graph. Then G is col-critical if and only if the vertex set of G can be partitioned into two sets V 1 and

V 2 such that G = G 1 + G 2 , where G i := G[V i ] for i ∈ {1, 2}, G 1 is regular, and (i) V (G 2 ) \ V δ (G 2 ) is an independent set of G 2 , and δ(G 1 ) + n(G 2 ) = δ(G 2 ) + n(G 1 )
or (ii) G 2 is an edgeless graph, and

n(G 1 ) -δ(G 1 ) -n(Q) < n(G 2 ) < n(G 1 ) -δ(G 1 )
where Q denotes a smallest component of G 1 (in terms of the number of vertices).

Moreover, col(G) = δ(G 1 ) + n(G 2 ) + 1 in both (i) and (ii).

Double-col-critical graphs

The analogue of the Double-Critical Graph Conjecture with χ replaced by col does not hold. For instance, the non-complete graph C 2 6 is 4-regular, 5-col-critical, and double-col-critical. Since C 2 6 is planar, it also follows that it is not even true that every double-col-critical graph with colouring number 5 contains a K 5 minor. (In [START_REF] Kawarabayashi | Double-critical graphs and complete minors[END_REF], it was proved that every double-critical graph G with χ(G) ≤ 7 at least contains a K χ(G) minor.) It is easy to see that the square of any cycle of length at least 5 is a double-col-critical graph with colouring number 5.

Observation 7 Any double-col-critical graph is col-vertex-critical.

Proof: Let G denote a double-col-critical graph. If there are no vertices in G, then we are done. Let v denote an arbitrary but fixed vertex of G. If there is no vertex in G adjacent to v, then we are done, since then, by the connectedness of G, G is just the singleton

K 1 . Let u denote a neighbour of v. By Observation 4, we need to show col(G -v) < col(G). The fact that G is double-col-critical implies col(G -u -v) ≤ col(G) -2. Suppose col(G -v) ≥ col(G). Then col((G -v) -u) ≤ col(G) -2 = col(G -v) -2
which contradictions Observation 3. This shows col(G -v) is strictly less than col(G), as desired.

2

Observation 8 For each integer k ∈ {0, 1, 2, 3, 4}, the only double-col-critical graph with colouring number k is the k-clique.

-v. Now G[{x, y, v}] is a 3-clique in G -t -u and so col(G -t -u) ≥ col(G[{x, y, v}]) = 3, a contradiction. This completes the proof. 2
It is easy to verify that the graphs Q 1 , Q 2 , and Q 3 in Figure 1 are double-col-critical and have colouring number 5. None of the graphs Q 1 , Q 2 , and Q 3 are squares of a cycle. We shall see that Q 1 , Q 2 , Q 3 , and the squares of the cycles of length at least 5 are all the double-col-critical graphs with colouring number 5. First a few preliminary observations. Observation 9 If G is a double-col-critical graph, then δ(G) = col(G) -1 and every pair of adjacent vertices of G has a common neighbour of degree δ(G) in G.

Proof: Let G denote a double-col-critical graph. Then, by Observation 7, G is also col-vertex-critical, and so, by Observation 6, δ(G) = col(G) -1. Let xy denote an arbitrary edge of G. Now, by the definition of the colouring number, G -x -y has minimum degree at most (col(G) -2) -1 which is equal to δ(G) -2. This means that some vertex of V (G) \ {x, y}, say z, which has degree at least δ

(G) in G has (a) The graph Q 1 . (b) The graph Q 2 . (c) The graph Q 3 .
Fig. 1: The graphs Q1, Q2, and Q3, depicted above, are the only double-col-critical graphs with colouring number 5 which are not squares of cycles.

degree at most δ(G) -2 in G -x -y. The only way this can happen is if z has degree δ(G) in G and is adjacent to both x and y in G. This completes the argument. 2

Observation 10 If G is a non-complete double-col-critical graph, then G does not contain a clique of order col(G) -1.

Proof: Let G denote a non-complete double-col-critical graph. By Observation 7, G is col-vertex-critical, and so, since G is also non-complete, G cannot contain a clique of order more than col(G) -1. Also, by Observation 7,

δ(G) = col(G) -1. Suppose that G contains a clique K of order col(G) -1. Clearly, G-V (K) is not empty. If G-V (K) contains an edge xy, then col(G)-1 = col(K) ≤ col(G-x-y) ≤ col(G) -2, a contradiction. Hence G -V (K) is edgeless, and so, since δ(G) = col(G) -1 = n(K), it follows that each vertex of V (G) \ V (K)
is adjacent to every vertex of V (K), in particular, G contains a clique of order col(G), a contradiction. 2

Proposition 3 Every double-col-critical graph with colouring number at least 3 is 2-connected.

Proof: Let G denote a double-col-critical graph with col(G) ≥ 3. Since G is col-vertex-critical, it is connected with col(G) = δ(G) + 1. Suppose G is not 2-connected, and let x denote a cutvertex of G. Each component of G-x has minimum degree at least δ(G)-1. Let C denote a component of G-x,
and let e denote some edge of G -V (C). Then, using the fact that G is double-col-critical, col is monotone, and C is a subgraph of G -V (e), we obtain

col(G) -1 = (δ(G) + 1) -1 ≤ col(C) ≤ col(G -V (e)) = col(G) -2
a contradiction. This shows that G must be 2-connected. 2

2.1 Double-col-critical graphs with colouring number 5.

We shall say that a k-neighbour of a vertex x is a neighbour of x of degree k. This contradiction implies that G contains no two adjacent vertices both of which have degree greater than 4.

2 Recently, the first author obtained a characterisation of what he called minimal critical graphs with minimum degree 4. It turns out that our double-col-critical graphs with colouring number 5 are such graphs, and so -using the characterisation of minimal critical graphs of minimum degree 4 -we obtain a characterisation of the double-col-critical graphs with colouring number 5.

In the following result, which is the main result of this paper, we let Q 1 , Q 2 , and Q 3 denote the graphs depicted in Figure 1.

Theorem 1 A graph is double-col-critical with colouring number 5 if and only if it is isomorphic to Q 1 , Q 2 , Q 3 ,
or the square of a cycle of length at least 5.

The graph Q 2 is the dual of the Herschel graph which is the smallest nonhamiltonian polyhedral graph. In order to prove Theorem 1, we first need to introduce a bit of notation and state the above-mentioned characterisation of minimal critical graphs with minimum degree 4.

For the remaining part of this section we shall be using the following notation. We shall let C denote the set of simple connected graphs of minimum degree at least 4. An edge e of a graph G in C is essential if the graph G -e obtained from G by deleting e is not in C, and let us call e critical if the graph G/e obtained by contracting e and simplifying is not in C. An edge e is essential if and only if e is a bridge or at least one of its endvertices has degree 4; and e is critical if and only if the endvertices of e have a common 4-neighbour or N (V (e), G) consists of three common neighbours of the endvertices of e. We are now interested in the minimal critical graphs in C, that is, graphs G ∈ C with the property that each edge of G is both essential and critical.

For the description of the minimal critical graphs in C, we shall consider a number of bricks, that is, any graph isomorphic to one of the following nine graphs:

K 5 , K 2,2,2 , K - 5 , K - 2,2,2 , K 5 , K 2,2,2 , K 5 , K 2
,2,2 , or K 3 which are depicted in Figure 2. Each brick comes together with its vertices of attachment: For K 5 and K 2,2,2 , this is an arbitrary single vertex, for the other seven bricks these are its vertices of degree less than 4. The remaining vertices of the brick are its internal vertices, and the edges connecting two inner vertices are called its internal edges. Observe that every brick B has one, two, or three vertices of attachment, and that they are pairwise nonadjacent unless B is the triangle, that is, K 3 .

It turns out that the minimal critical graphs from C are either squares of cycles of length at least 5, or they are the edge disjoint union of bricks, following certain rules. This is made precise in the following

K5 K2,2,2 K - 5 K - 2,2,2 K 2,2,2 K 5 K 2,2,2 K 5 K3
Fig. 2: The nine bricks. Vertices of attachment are displayed solid.

theorem.

Theorem 2 (Kriesell [START_REF] Kriesell | Nonseparating K4-subdivisions in graphs of minimum degree at least 4[END_REF]) A graph is a minimal critical graph in C if and only if it is the square of a cycle of length at least 5 or arises from a connected multihypergraph H of minimum degree at least 2 with at least one hyperedge and |V (e)| ∈ {1, 2, 3} for all hyperedges e by replacing each hyperedge e by a brick B e (see Figure 2) such that the vertices of attachment of B e are those in V (e) and at the same time the only objects of B e contained in more than one brick, and

(TB) the brick B e is triangular only if each vertex x ∈ V (e) is incident with precisely one hyperedge f x different from e and the corresponding brick

B fx is neither K 5 , K - 5 , K 2,2,2 , nor K - 2,2,2
, and, for any other vertex y ∈ V (e) \ {x} and hyperedge f y containing y but distinct from e, we have

(i) V (f x ) ∩ V (f y ) = ∅ only if not both of B fx
and B fy are triangular, and

(ii) f x = f y only if B fx is K 5 or K 2,2,2 .
Proof of Theorem 1.: In order to prove the desired result, we prove the following equivalent statement.

A graph is double-col-critical with colouring number 5 if and only if it is the square of a cycle of length at least 5 or one of the three graphs obtained by taking the union of two graphs G 1 and G 2 such that

G i K 5 or G i K 2,2,2 for i ∈ {1, 2} and x ∈ V (G 1 ) ∩ V (G 2 ) if and only if x has degree 2 in G 1 and degree 2 in G 2 .
The 'if'-part of the statement above is straightforward to verify and it is left to the reader.

Let G denote an arbitrary double-col-critical graph with colouring number 5. It follows from the definition of double-col-critical graphs, Observation 6, Observation 7, Observation 9, and Observation 11 that G has the following properties. By (a), G is in C. By (b), every edge of G is essential, and, by (c), every edge of G is critical. Thus, G is minimal critical in C, and so Theorem 2 applies. Suppose that G is not the square of a cycle. Then G has a representation by a multihypergraph H as described in Theorem 2.

If e is a 1-hyperedge then the unique attachment vertex of the corresponding brick B e in G is a cutvertex of G, a contradiction to Proposition 3.

Suppose that there exists a 2-hyperedge e with V (e) = {u, v}. Suppose that H contains a 3-hyperedge e for which the corresponding brick B e is triangular. It follows from (a) and (d) that some vertex q ∈ V (G) \ V (B e ) is adjacent to at least two vertices in V (B e ). The vertex q is not adjacent to all three vertices of V (B e ), since otherwise G[V (B e ) ∪ {q}] would induce a 4-clique in G which contradicts Observation 10. Let x and y denote the neighbours of q in V (B e ). By Theorem 2 (TB), x is incident to exactly one hyperedge f x different from e. Similarly, y is incident to exactly one hyperedge f y different from e. If f x = f y , then, by Theorem 2 (TB.ii), B fx is K 5 or K 2,2,2 , in particular, f x is a 2-hyperedge, a contradiction. Hence f x = f y and so, since q ∈ V (f x ) ∩ V (f y ), it follows from Theorem 2 (TB.i) that not both B fx and B fy are triangular bricks. The fact that f x and f y are distinct and q ∈ V (f x ) ∩ V (f y ) implies that q is an attachment vertex of both B fx and B fy . Since q is adjacent to x and both q and x are attachment vertices, it follows that B fx must be triangular. Similarly, B fy must be triangular, and so we have obtained a contradiction. This shows that each hyperedge in H is of the type K 5 or K 2,2,2 .

If B e is K 5 or K 2,2,2 then B e -V (
Let e denote an arbitrary 3-hyperedge of H. If there are two vertices x, y ∈ V (e) of degree exceeding 4 in G then G -(V (B e ) \ {x, y}) has minimum degree at least 3, contradicting (d) applied to any internal edge of B e . Therefore, if there is a vertex x ∈ V (e) of degree exceeding 4 in G, then the two vertices y, z ∈ V (e)\{x} are incident with precisely one further 3-hyperedge f y and f z , respectively, both distinct from e. If f y = f z then one may argue as above that G -V (B e -x) has minimum degree at least 3, contradicting (d) applied to any internal edge of B e . Hence f y = f z =: f . Let w be the vertex in V (f ) \ {y, z}. If w = x then {w, x} forms a 2-separator, and otherwise w = x is a cutvertex as x has degree exceeding 4. In either case, G -(V (B e -x) ∪ V (B f )) has minimum degree at least 3, again contradicting (d).

Hence all vertices of attachment have degree 4 in G. Let e denote a 3-hyperedge in H, and let x, y, and z denote the vertices of V (e). Again let f x , f y , f z denote the unique 3-hyperedge distinct from e incident with x, y, z, respectively. If they are pairwise distinct then G -V (B e ) has minimum degree at least 3, contradiction to (d). If f := f y = f z = f x then let w be the vertex in V (f ) distinct from y, z. As f x = f , we have w = x, so that G -(V (e) ∪ V (f )) has minimum degree at least 3, contradicting (d), unless there is a vertex in V (f x ) adjacent to both x and w; in this latter case, the unique 3-hyperedge distinct from f incident with w must be f x , and so the vertex u in V (f x ) \ {w, x} is a cutvertex of G, a contradiction to Proposition 3. Hence f x = f y = f z , and the desired statement follows.

2 Given our success in characterising the double-col-critical graphs with colouring number 5, we venture to ask for a characterisation of the double-col-critical graphs with colouring number 6.

If G is a double-col-critical graph, then G + K k is a double-col-critical graph with col(G + K k ) = col(G) + k (see Proposition 4).
This implies that the graphs

Q 1 + K 1 , Q 2 + K 1 , Q 3 + K 1 , and C + K 1 ,
where C is the square of any cycle of length at least 5, are all double-col-critical graphs with colouring number 6. These are not the only double-col-critical graphs with colouring number 6; the icosahedral graph is yet another doublecol-critical graph with colouring number 6. This latter fact was also observed by Stiebitz [18,p. 323], although in a somewhat different setting. Using the computer programs SAGE [START_REF] Stein | Sage Mathematics Software (Version 4.6.2)[END_REF] and geng [START_REF] Mckay | geng -a program for generating graphs[END_REF], we determined all the double-col-critical graphs with colouring number 6 and at most 10 vertices; there are 116 such graphs and they are available at the second authors homepage [START_REF] Pedersen | [END_REF]. The standard 6-regular toroidal graphs obtained from the toroidal grids by adding all diagonals in the same direction have colouring number 7 and are double-col-critical.

Complete joins of double-col-critical graphs. In [START_REF] Kawarabayashi | Double-critical graphs and complete minors[END_REF], it was observed that if G is the complete join G 1 + G 2 , then G is double-critical if and only if both G 1 and G 2 are double-critical. Next we prove that the 'if'-part of the analogous statement for double-col-critical graphs is true. The 'only if'-part is not true, as follows from considering the double-col-critical graph C 2 6 : We have

C 2 6 C 4 + K 2 but neither C 4 nor K 2 is double-col-critical. Proposition 4 If G 1 and G 2 are two disjoint double-col-critical graphs, then the complete join G 1 + G 2 is also double-col-critical with col(G 1 + G 2 ) = min{col(G 1 ) + n(G 2 ), col(G 2 ) + n(G 1 )} Proof:
Let G 1 and G 2 denote two disjoint double-col-critical graphs. Then, by Observation 7, both G 1 and G 2 are col-vertex-critical, and so, by Proposition 1,

col(G 1 + G 2 ) = min{col(G 1 ) + n(G 2 ), col(G 2 ) + n(G 1 )}
We need to prove that col((G 1 + G 2 ) -x -y) ≤ col(G 1 + G 2 ) -2 for every edge e = xy ∈ E(G); by symmetry, it suffices to consider [START_REF] Bondy | Graph Theory[END_REF] x, y ∈ V (G 1 ) and ( 2

) x ∈ V (G 1 ) and y ∈ V (G 2 ). Suppose x, y ∈ V (G 1 ). Then col((G 1 + G 2 ) -x -y) = col((G 1 -x -y) + G 2 ) ≤ min{col(G 1 -x -y) + n(G 2 ), col(G 2 ) + n(G 1 -x -y)} ≤ min{col(G 1 ) -2 + n(G 2 ), col(G 2 ) + n(G 1 ) -2} = min{col(G 1 ) + n(G 2 ), col(G 2 ) + n(G 1 )} -2
where we applied Proposition 1 and the fact that G 1 is double-col-critical. A similar argument applies in case [START_REF] Erdős | Problem 2. In Theory of Graphs[END_REF]. We omit the details.

2 Proposition 4 and the fact that both C 2 6 and K t are double-col-critical immediately implies the following result, which, in particular, shows that, for each integer k ≥ 6, there is a non-regular double-col-critical graph with colouring number k.

Corollary 1 For any positive integer t, the graph

G t := C 2 6 + K t is a double-col-critical graph with col(G t ) = t + 5, δ(G t ) = n(G t ) -2 and ∆(G t ) = n(G t ) -1.

Double-col-critical edges

In [START_REF] Kawarabayashi | Double-critical graphs and complete minors[END_REF], Kawarabayashi, the second author, and Toft initiated the study of the number of double-critical edges in graphs. In this section, we study the number of double-col-critical edges in graphs. Kawarabayashi, the second author, and Toft proved the following theorem for which we shall prove an analogue for the colouring number.

The complete join C n + K 1 of a cycle C n and a single vertex is referred to as a wheel, and it is denoted W n . If n is odd, we refer to W n as an odd wheel.

Theorem 3 (Kawarabayashi, Pedersen & Toft [START_REF] Kawarabayashi | Double-critical graphs and complete minors[END_REF]) If G denotes a 4-critical non-complete graph, then G contains at most m(G)/2 double-critical edges. Moreover, G contains precisely m(G)/2 doublecritical edges if and only if G is an odd wheel of order at least 6.

The following result is just a slight reformulation of Theorem 3.

Corollary 2 If G denotes a 4-chromatic graph with no 4-clique, then G contains at most m(G)/2 doublecritical edges. Moreover, G contains precisely m(G)/2 double-critical edges if and only if G is an odd wheel of order at least 6.

Proof: Let G denote a 4-chromatic graph with no 4-clique. If e = xy is a double-critical edge in G, then e is a critical edge of G and x is a critical vertex of G. We remove non-critical elements from G until we are left with a 4-critical subgraph G . At no point did we remove an endvertex of a double-critical edge. Thus, the number of double-critical edges in G is equal to the number of double-critical edges in G . Clearly, G is a non-complete graph, and so, by Theorem 3, the number of double-critical edges in G is at most m(G )/2 which is at most m(G)/2. The second part of the corollary now follows easily.

2

The following result -which is an analogue of Theorem 3 with the chromatic number replaced by the colouring number -extends Observation 8.

Proposition 5 If G denotes a 4-col-critical non-complete graph, then G contains at most m(G)/2 doublecol-critical edges. Moreover, G contains precisely m(G)/2 double-col-critical edges if and only if G is a wheel of order at least 6.

Lemma 1 If e and f are two double-col-critical edges in a 4-col-critical non-complete graph, then e and f are incident.

Proof: Let G denote a col-critical graph with col(G) = 4. Then, by Observation 5, δ(G) = 3. We must have ω(G) ≤ 3, since G is a 4-col-critical non-complete graph. Suppose e is an arbitrary double-col-critical edge in G. Then col(G -V (e)) = 2 which, by Observation 1 (iii), means that G -V (e) is a forest containing at least one edge and, since δ(G) = 3, δ(G -V (e)) ≥ 1 and each leaf in G -V (e) is adjacent to both endvertices of e in G. Let u and v denote two leafs of G -V (e). Now, if G contains some double-col-critical edge f which is not incident to e, then G -V (f ) contains no cycles, since col(G -V (f )) = 2, and so f is incident to both u and v, which implies G[{u, v} ∪ V (e)] K 4 , a contradiction. This means that any two double-col-critical edges of G are incident, and the proof is complete. G). We may assume that there is at least one double-col-critical edge, say, vw in G. Suppose G -v is disconnected. Then, since δ(G) = 3, each component of G -v has minimum degree at least 2, and so, in particular, some component of G -v -w has minimum degree at least 2. This, however, contradicts the fact that G -v -w is a forest. Hence G -v is connected. By Observation 3, col(G -v) ≥ 3 and so, by Observation 1 (iii), G -v contains a cycle. Hence G -v is a connected graph with at least one cycle, and so m

(G -v) ≥ n(G -v). Thus, m(G) = deg(v, G) + m(G -v) ≥ deg(v, G) + (n(G) -1) ≥ 2 deg(v, G)
which implies that the number of double-col-critical edges is at most m(G)/2 and that the number of double-col-critical edges is equal to m(G)/2 only if deg(v, G) = n(G) -1 and G -v is a cycle. Conversely, if G is a wheel on at least five vertices, then it is easy to see that exactly m(G)/2 edges of G are double-col-critical. This completes the proof.

2 Let k denote some integer greater than 3. Let D k denote the 2k-cycle with vertices labelled cyclically v 3 depicts a drawing of F 5 .

0 v 1 . . . v k u k-1 u k-2 . . . u 1 . Let F k denote the graph D 2 k -u 1 v 1 -u k-1 v k-1 + v 1 v k-1 + u 1 u k-1 Figure
Observation 12 For every integer k greater than 3, the graph F k , as defined as above, is a 5-col-critical graph with colouring number 5 in which all edges except v 1 v k-1 and u 1 u k-1 are double-col-critical.

Proposition 6 For each integer p greater than 4 and positive real number , there is a p-col-critical graph G with the ratio of double-col-critical edges between 1and 1.

Proof: If p = 5, the desired result follows directly from Observation 12 by letting k tend to infinity. Let p denote an integer greater than 5 and a positive real number. Let k denote an integer a lot greater than p, and let G denote the graph obtained by taking the complete join of F k and K p-5 . Then, by

v 0 v 2 v 3 v 5 u 2 u 3 u 1 v 1 u 4 v 4
Fig. 3: The graph F5 has colouring number 5 and all edges of F5, except u1v4 and v1u4, are double-col-critical.

Proposition 2 (ii), G is p-col-critical, and, since k is a lot greater than p, all but the edges v 1 v k-1 and u 1 u k-1 are double-col-critical in G. By letting k tend to infinity the ratio of double-col-critical edges in G will from a certain point onwards be between 1and 1. This completes the argument. 2

Proposition 6 means that there is no result corresponding to Proposition 5 for colouring numbers greater than 4.

Concluding remarks

By a theorem of Mozhan [START_REF] Mozhan | Twice critical graphs with chromatic number five[END_REF] and, independently, Stiebitz [START_REF] Stiebitz | K5 is the only double-critical 5-chromatic graph[END_REF], K 5 is the only double-critical graph with chromatic number 5, that is, K 5 is the only 5-chromatic graph with 100% double-critical edges, but we do not know whether there are non-complete 5-chromatic graphs with the percentage of double-critical edges arbitrarily close to a 100. In [START_REF] Kawarabayashi | Double-critical graphs and complete minors[END_REF], Kawarabayashi, the second author, and Toft conjectured that if G is a 5-critical non-complete graph, then G contains at most (2 + 1 3n(G)-5 ) m(G) 3 double-critical edges. As we have seen, the story is a bit different for the colouring number. By Proposition 6 for p = 5, there are non-complete graphs with colouring number 5 with the percentage of double-col-critical edges arbitrarily close to a 100. This only makes Theorem 1 all the more interesting. By Theorem 1, we are able to distinguish between graphs with colouring number 5 having 99.99% double-col-critical edges and those that have a 100% double-col-critical edges.

The problem of obtaining a concise structural description of the double-col-critical graphs with colouring number k ≥ 6 remains open. Given any graph G, it can be decided in polynomial time whether or not G is double-col-critical, since the colouring number itself can be computed in polynomial time. Nevertheless, given the structural complexity of the double-col-critical graphs with colouring number 6 mentioned on page 58, it seems likely that even the problem of obtaining a concise structural description of the double-col-critical graphs with colouring number 6 is non-trivial.

Proof:

  Let G denote a double-col-critical graph, and define k := col(G). Then, by Observation 7, G is also col-vertex-critical, and so, by Observation 6, δ(G) = k -1. If k ≤ 3, then the desired result follows immediately from Observation 2. Suppose k = 4. Then, for any edge e ∈ E(G), col(G -V (e)) ≤ 2 and so, by Observation 1, G -V (e) is a forest. Fix an edge xy ∈ E(G). If G -x -y contains no edges, then G is 2-degenerate and so col(G) ≤ 3, a contradiction. Let T denote a component of G -x -y with at least one edge, and let u and v denote two leafs of T . Since, as noted above, δ(G) = 3, it follows that both u and v are adjacent to both x and y. If u and v are adjacent in T , then G[{u, v, x, y}] K 4 , and so, since G is also col-vertex-critical, G K 4 . Hence we may assume that u has a neighbour t in T

Observation 11

 11 If G is a double-col-critical graph with colouring number 5 and ab ∈ E(G), then a or b has degree 4 in G.Proof: Let G denote a double-col-critical graph with colouring number 5. Then δ(G) = 4. Let ab denote an edge of G. Suppose that both a and b have degree greater than 4 in G. By Observation 9, there is a common 4-neighbour c of a and b. We shall make repeated use of Observation 9 and Observation 10. The latter observation implies that G contains no 4-clique. There is a common 4-neighbour d of a and c. Since ω(G) ≤ 3, d is not adjacent to b. This implies that there is a common 4-neighbour e of b and c and e is not identical to d. The vertex e is not adjacent to a. The vertex a has degree at least 5, and so the common 4neighbour of c and d must be e. We note that {a, b, c, d, e} induces a subgraph of G of minimum degree 3. Hence G-{a, b, c, d, e} contains no edges. Moreover, col(G-{c, d, e}) ≤ col(G)-2, and so G-{c, d, e} contains a vertex f of degree at most 2. Since a and b both have degree at least 3 in G -{c, d, e} and N (c, G) = {a, b, d, e}, it follows that this vertex f must be in the set V (G) \ {a, b, c, d, e} and that f is adjacent both d and e. The vertex f has degree 4 in G. It also follows from the fact that G -{a, b, c, d, e} contains no edges that f must be adjacent to both a and b. Since a has degree at least 5 in G, it follows that a must be adjacent to some vertex g ∈ V (G) \ {a, b, c, d, e, f }. Then col(G -a -g) ≤ col(G) -2 = 3. On the other hand, {b, c, d, e, f } induce a subgraph of G -a -g of minimum degree 3, a contradiction.

(a) G has minimum degree 4 ;

 4 (b) if x and y are adjacent vertices, then at least one of them has degree 4;(c) if x and y are adjacent vertices, then they have a common 4-neighbour; and (d) if x and y are adjacent in G, then G -x -y has no induced subgraph of minimum degree at least 3.

  e) is an induced subgraph of G of minimum degree 3, and since the vertex u ∈ V (e) has only two neighbours in that subgraph, there is an edge in G -(V (B e ) \ V (e)), contradicting (d). If, otherwise, B e is K - 5 or K - 2,2,2 then, by Theorem 2, B e is an induced subgraph of G of minimum degree 3. By (a), there is a vertex in V (G) \ V (B e ), and it has a neighbour in V (G) \ V (B e ). This contradicts (d). Hence there are only 3-hyperedges in H.

  Observation 1 For any graph G, (i) col(G) = 0 if and only if G is the empty graph, (ii) col(G) = 1 if and only if G contains at least one vertex but no edges, (iii) col(G) = 2 if and only if G is forest containing at least one edge, and

Acknowledgements

We thank Bjarne Toft for posing the problem of characterising the double-col-critical graphs and his many insightful comments on colouring and degeneracy of graphs.