text:
Pierre Charbit
email: charbit@irif.fr

Geňa Hahn
email: hahn@iro.umontreal.ca

Marcin Kamiński

Manuel Lafond
email: manuel.lafond@usherbrooke.ca

Nicolas Lichiardopol
email: nicolas.lichiardopol@neuf.fr

Reza Naserasr

Ben Seamone
email: seamone@iro.umontreal.ca

Rezvan Sherkati
email: rezvan.sherkati@mail.mcgill.ca

| Ge Ňa Hahn

| Ben Seamone

Jacobson, Kézdy, Lehel, Schein- G Chen

Edge clique covers in graphs with independence number two

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

Throughout, G = (V , E ) refers to a simple loopless graph and n denotes the number of vertices in G when the graph in question is clear. Standard graph theory notation is used throughout, but we make the following definitions explicit.

We denote by G [X ] the subgraph of G induced by X ⊆ V (G ). A clique is a set Q ⊆ V (G ) such that G [Q ] is a complete graph. The edge clique cover number of a graph G , denoted ecc(G ), is the minimum number of complete subgraphs of G whose union contains every edge of G . This parameter, also known as the intersection number of a graph, was introduced by Erd ős, Goodman, and Posa [START_REF] Erd Ős | The representation of a graph by set intersections[END_REF]. In addition to being an interesting parameter in its own right, it is also related to a parameter known as the competition number of a graph, introduced by Cohen [START_REF] Cohen | Interval graphs and food webs: a finding and a problem[END_REF] in the study of food webs.

We begin with the following problem: Problem 1.1 (Chen, Jacobson, Kézdy, Lehel, Scheinerman, Wan [START_REF] Chen | Clique covering the edges of a locally cobipartite graph[END_REF]) If G is a claw free graph, is ecc(G ) ≤ n?

As evidence, it was shown in [START_REF] Chen | Clique covering the edges of a locally cobipartite graph[END_REF] that the answer is "yes" in the special case of quasi-line graphs (graphs where the neighborhood of any vertex can be partitioned into two cliques), a question which was of interest from the point of view of competition numbers of graphs. Recently, Javadi and Hajebi [START_REF] Javadi | Edge clique cover of claw-free graphs[END_REF] have given an affirmative answer to Problem 1.1 when α(G ) ≥ 3. Their result relies heavily on Chudnovsky and Seymour's structure theorem for claw-free graphs (see [START_REF] Chudnovsky | The structure of claw-free graphs[END_REF]), which only applies to graphs with α(G ) ≥ 3. Since their techniques cannot be extended to the case of α(G ) = 2, Problem 1.1 is reduced to the following conjecture, which is the focus of our study in this paper:

Conjecture 1 If G is a graph with α(G ) = 2, then ecc(G ) ≤ n.
Our work is organized as follows. Section 2 contains our main results on ecc(G ), where we improve upon the previously best known bound of ecc(G ) ≤ cn 4/3 log1/3 n if α(G ) = 2, given by Javadi, Maleki, and Omoomi in [START_REF] Javadi | Local Clique Covering of Claw-Free Graphs[END_REF] 1 . We also show how our results can be used to obtain even better bounds for fractional edge clique covers. In Section 3, we consider the dual problem of packing edges with respect to cliques. In Section 4, we present some basic observations about graphs of independence number 2 and use them to derive properties that any minimal counterexample to Conjecture 1 must have, if one exists. Finally, in Section 5, we examine ecc(G ) for some interesting subclasses of graphs with independence number 2; in particular, we consider forbidden induced subgraphs, the complete joins of graphs, and graphs with bounded diameter.

| IMPROVED UPPER BOUNDS

| Edge clique cover number

We begin with the following simple lemma. Given a graph G , we say that an edge e ∈ E (G ) is a dominating edge if every v ∈ V (G ) is adjacent to an end of e. The proof of our main result relies on the two following lemmas:

Lemma 2.2 If G with α(G ) ≤ 2 has no dominating edge, then ecc(G ) ≤ n.
Proof The hypothesis on G implies that the ends of any edge of G belongs to some N (x ). Hence the collection of all non-neighborhoods constitutes a family of n cliques (by Lemma 2.1) that cover all edges of the graph.

Lemma 2.3

Let G be a graph with α(G ) = 2. For an edge e ∈ E (G ), α(Ge) > α(G ) if and only if e is not a dominating edge.

Proof Let x and y be the endpoints of e. First we prove that if e is not a dominating edge, then α(Ge) > α(G ). Since e is not a dominating edge, there exists a vertex v ∈ V (G ) such that xv E (G ) and yv E (G ). Thus, in graph Ge the set {x, y , v } is an independent set. Therefore, α(Ge) ≥ 3 > 2 ≥ α(G ). Now, we prove that if e is a dominating edge, then α(Ge) = α(G ). Since for every v ∈ V (G ), v is adjacent to at least one of x or y , no independent set of size 3 can contain x and y in Gx y . Thus, α(Ge) = α(G ).

In [START_REF] Javadi | Local Clique Covering of Claw-Free Graphs[END_REF], it is shown that there is a constant c such that ecc(G ) ≤ cn 4/3 log 1/3 n if α(G ) = 2. By applying Lemmas 2.2 and 2.3, we obtain the following general theorem, which implies a linear upper bound for ecc(G ) in terms of n. Recall that the vertex cover number of a graph G , denoted β (G ), is the cardinality of a smallest set of vertices which is incident to every edge of G .

Theorem 2.4 Let G be a graph with α(G ) = 2. If G is a minimal spanning subgraph with α(G ) = 2, then ecc(G ) ≤ n + β (G -E (G )). Proof Let D = E (G ) \ E (G ) and let G D = (V (G ), D ) (or, equivalently, G D = G -E (G )).
v ∈ V (G ), every edge of D is incident to a vertex of N G [v ]. Let v be a vertex of minimum degree. If some edge of D is incident to v , d G (v ) ≤ δ(G ) -1 and so N G [v ] is a vertex cover for G D of cardinality at most (δ(G ) -1) + 1 = δ(G ).
On the other hand, if no edge of D is incident to v , then in fact N G (v ) suffices for our vertex cover, which also has cardinality at most δ(G ).

Corollary 2.6 If G is a graph with α(G ) = 2, then ecc(G ) ≤ 2n -c n log n for some absolute constant c > 0.
Proof Again, let G , D , and G D be as in the proof of Theorem 2.4. If the vertices x, y , z form a triangle in G D , then {x, y , z } is an independent set in G . By our choice of G to have α(G ) = 2, it follows that G D is triangle-free. It is known that every triangle-free graph has an independent set of size Ω( n log n) [START_REF] Ajtai | A note on Ramsey numbers[END_REF]. Since the complement of an independent set is a vertex cover, we get an upper bound of nc n log n for the size of a vertex cover of G D , and so G has an edge clique cover of size at most 2nc n log n.

Corollary 2.6 makes explicit use of the lower bound known on the Ramsey number R (3, t ) (the minimum value of n such that every n-vertex graph contains either a clique of size 3 or an independent set of size t ). It is worth noting that this bound was shown to be tight by a famous theorem of Kim [START_REF] Kim | The Ramsey number R (3, t ) has order of magnitude t 2 /log t[END_REF], and so any significant improvement to the bound given in Corollary 2.6 will almost certainly require a different approach than that of Theorem 2.4.

| Fractional edge clique covers

Consider the fractional version of the problem. A graph G has a fractional edge clique cover of size k if there exists a set of cliques Q and a real-valued weight function w such that

1. w (Q ) ≥ 0 for all Q ∈ Q, 2. Q : e ∈E (G [Q ])
w (Q ) ≥ 1 for each e ∈ E (G ), and

3. Q ∈Q w (Q ) = k .
The fractional edge clique cover number of a graph G , denoted ecc f (G ) and first studied in [START_REF] Scheinerman | On the Fractional Intersection Number of a Graph[END_REF], is the smallest k such that G has a fractional edge clique cover of size k . The proof of Theorem 2.4 is easily modified to give an upper bound on ecc f (G ) which is an improvement on its integer counterparts.

Theorem 2.7 If G is a graph with α(G ) = 2, then ecc f (G ) ≤ 3 2 n.
Proof Let G , G , and D be as in the proof of Theorem 2.4. As before, we begin with an edge clique cover of G of size at most n. Instead of taking a vertex cover for D , we take the set

{K v | v ∈ V (G )}.
Note that each edge of D is covered twice by {K v }. Thus, by assigning weight 1 to the cliques covering G and weight 1 2 to each K v , we obtain the desired result.

| EDGE PACKING WITH RESPECT TO CLIQUES

A set of edges E ⊆ E (G ) is called an edge packing with respect to cliques (which we will simply call a packing for the remainder of this work) if for any two distinct edges e 1 , e 2 ∈ E , no clique of G contains both e 1 and e 2 . The packing number of G , denoted pack(G ), is the maximum size of a packing of G . Since no clique of G can cover two edges of a packing, ecc(G ) ≥ pack(G ). Indeed, it is easy to see that if we consider the edge clique cover problem as an integer program, then the edge packing problem is its dual. It thus easily follows that pack(G

) ≤ pack f (G ) = ecc f (G ) ≤ ecc(G ).
We begin with two simple observations.

Proposition 3.1 If F is a packing of G and v ∈ V (G ), then v is incident to at most α(G ) edges that belong to F . Proof Denote by G F = (V , F ) the graph G restricted to F . The neighborhood of v in G F must form an independent set
in G , as otherwise two packed edges would belong to a common triangle. This leads us to an easy to obtain upper bound on pack(G ) in the case where α(G ) = 2.

Proposition 3.2 If G is a graph with α(G ) = 2, then pack(G ) ≤ n.
Proof By Proposition 3.1, each vertex v has at most 2 incident packed edges. By a handshaking argument, pack(G ) ≤ n.

One may tempted to conjecture that, should a counterexample exists to Conjecture 1, it should have very large packing number. The following theorem shows, perhaps somewhat surprisingly, that graphs with α = 2 and maximum possible packing number actually satisfy Conjecture 1.

Theorem 3.3 If α(G ) = 2 and pack(G ) = n, then ecc(G ) = n.
Proof Let F be a packing of n edges. By Proposition 3.1, every vertex is incident to exactly two edges of

F . For u, v ∈ V , denote N u,v = N G [u] ∩ N G [v ].
We prove that for every uv ∈ F , N u,v is a clique, and that the collection of cliques

{N u,v : uv ∈ F } covers E (G ).
Let v ∈ V (G ) be an arbitrary vertex, and let v 1 , v 2 ∈ V (G ) be such that vv 1 , vv 2 ∈ F (note that this implies that

v 1 v 2 E (G )). If v z ∈ E
for some z , then z must be a neighbor of at least one of v 1 or v 2 , for if not, {v 1 , v 2 , z } form an independent set. We now argue that z is adjacent to exactly one of v 1 and v 2 . Suppose that both v 1 z, v 2 z ∈ E . Let

z 1 , z 2 ∈ V (G ) be such that z z 1 , z z 2 ∈ F . Note that z 1 , z 2 must be distinct from v , as well as from v 1 , v 2 -if v i = z j for i , j ∈ {1, 2}, then vv i , zv i are both packed edges in the {v , v i , z } triangle, a contradiction. If z 1 is a neighbor of v , then as above, it must be also neighbor of v 1 or v 2 . Suppose w.l.o.g. that z 1 v 1 ∈ E . Then {v 1 , v , z, z 1 } form a clique, contradicting
that vv 1 and z z 1 are both packed edges. Therefore, v z 1 , and by the same argument v z 2 , cannot be edges, implying that {v , z 1 , z 2 } is an independent set, a contradiction. Thus, no neighbor of v is a common neighbour to both v 1 and v 2 ; in other words,

N v ,v 1 \ {v } are all non-neighbors of v 2 . This implies that N v ,v 1 \ {v } is a clique (since α(G ) = 2), and thus so is N v ,v 1 as claimed.
It remains to show that these cliques cover all edges of G . If v z ∈ E (G ), where z {v 1 , v 2 }, then exactly one of v 1 z and v 2 z is an edge of G , as argued above. In other words, every edge incident to v must lie either in the clique

N v ,v 1 or the clique N v ,v 2 . Thus {N u,v : uv ∈ F } covers E (G ).
We note that infinite families of graphs satisfying the conditions of Theorem 3.3 exist. Javadi and Hajebi [START_REF] Javadi | Edge clique cover of claw-free graphs[END_REF] show that the p th power of the cycle C 3p+1 has independence number 2 and edge clique cover number 3p + 1; it is easy to check that pairs of vertices at distance p around such a cycle are adjacent in C 3p+1 and these edges for a packing. This also shows that the bound in Proposition 3.2 cannot be improved upon.

| TOWARD A MINIMUM COUNTEREXAMPLE TO CONJECTURE 1

We now establish a number of lemmas, stated in their most general form, which will allow us to simply state a number of properties that any vertex-minimal counterexample to Conjecture 1 must possess, if such a graph exists. gives a collection of at most n cliques that cover every edge.

Lemma 4.1 If G is a graph with α(G ) = 2 and u ∈ V (G ) is an arbitrary vertex, then 1. ecc(G ) = ecc(G -u) + k if d (u) = n -1, where k denotes the number of isolated vertices in G -u; 2. ecc(G ) ≤ ecc(G -u) + 1 if u is simplicial (i.e. if N (u) is a clique); 3. ecc(G ) ≤ ecc(G [N (u)]) + + d (u) + 1 if 1 < d (u) < n -1, where denotes the number of isolated vertices in G [N (u)]; 4. ecc(G ) ≤ 2d (u) + 1 if ecc(G [N (u)]) ≤ d (u); 5. ecc(G ) ≤ n if δ(G ) ≤ n-
Lemma 4.5 Let G be a graph with α(G ) = 2. If X is a clique such that |X | ≥ n+1 2 and ecc(G -X ) ≤ |G -X |, then ecc(G ) ≤ n. Proof Let |X | = k . If v ∈ V (G -X
) has a neighbor in X , let G v be the graph induced by v and all its neighbors in X . The collection of all G v 's covers all edges from X to G -X , and so G has an edge clique cover of size at most

(n -k ) + (n -k ) + 1 ≤ 2n -2 n+1 2 + 1 = n. Lemma 4.6 If G is a graph with α(G ) = 2, X ⊂ V (G ) is a vertex cut, and ecc(G [X ]) ≤ |X | < n-1 3 , then ecc(G ) ≤ n. Proof Let |X | = k . Since α(G ) ≤ 2, G -X must
(G [N (u) ∩ N (v )]) ≤ |N (u) ∩ N (v ) | and |N (u) ∩ N (v ) | ≤ n-2 5 , then ecc(G ) ≤ n. Proof For two non-adjacent vertices u, v ∈ V , let N u = N (u) \ N (v ), N v = N (v ) \ N (u) and N uv = N (u) ∩ N (v ).
We denote the cardinalities of these sets by To cover the remaining edges of (N u , N v ), we choose the smaller of N u and N v (without loss of generality N u ), and for each z ∈ N u use the clique induced by {z } ∪ (N (z ) ∩ N v ). In total, the number of cliques used to cover E (G ) is

n u = |N u |, n v = |N v |, n uv = |N uv |. By Lemma 2.1, G [N u ∪ {u }] and G [N v ∪ {v }]
2 + n uv + 2n uv + min{n u , n v } ≤ 2 + n-2 5 + 2(n-2) 5 + 1 2 n -n-2 5 -2 ≤ n. Lemma 4.8 Let G be a graph with α(G ) = 2. If G contains a minimal vertex cut S such that G [S ] is disconnected, then ecc(G ) ≤ n 2 + 4.
Proof Suppose a subset S of V (G ) separates G into two cliques and is disconnected. If S induces a disconnected graph, then this graph has exactly two connected components which must be cliques. Then G consists of four pairwise disjoint cliques, say S 0 , S 1 , S 2 , S 3 , with S = S 0 ∪ S 2 and V (G ) \ S = S 1 ∪ S 3 and (S i , S i +2 ) = ∅ (addition modulo 4). Observe that S 1 ∪ S 3 is also a separating set of G and one of the two separating sets has at most half of the vertices of G . Without loss of generality, assume it is S . Further, each of the cliques S i is the union (as described above) of two sets of vertices, those adjacent to all of S i +1 and those adjacent to all of S i -1 . Let us denote these sets by S + i and S - i . Clearly the sets S i ∪ S + i -1 and S i ∪ S - i +1 induce cliques in G and cover most of the edges of G , in particular all the edges of the cliques induced by the S i . It remains to cover the edges between S i and S + i +1 and between S i and S - i -1 . This is quite easy since each vertex of S i only needs to cover the edges to at most one of S + i +1 and S - i -1 . The cliques consisting each of a vertex x ∈ S * j \ (S + j ∩ S - j ) for j = 0, 2, and its neighbors in S j * 1 ( * ∈ {+, -}) cover the edges that need to be covered and there are at most n 2 of them. Thus, ecc(G ) ≤ n 2 + 4.

From Lemmas 4.1 to 4.8, we may deduce the following:

Theorem 4.9 If G is a minimal counterexample to Conjecture 1, then 1. ∆(G ) < n -1; 2. δ(G ) ≥ n 2 -1; 3. G contains no vertices x, y such that N (x ) ⊆ N (y ) or such that N [x ] ⊆ N [y ];

κ(G ) ≥ n

3 and any minimal vertex cut induces a connected subgraph of G ; 5. ω(G ) ≤ n 2 ; 6. for any pair u, v of nonadjacent vertices, n uv > n-2 5 ;

Furthermore, since the proofs of Lemmas 4.1 to 4.8 are all inductive, Theorem 4.9 holds when restricted to any class G of graphs having some hereditary property P (in particular, for H -free graphs, which we consider in Section 5.3).

| COVERINGS IN PARTICULAR GRAPH CLASSES

This final section considers ecc(G ) for particular classes of graphs when restricted to those satisfying α(G ) = 2.

| Bounded vertex cover number

Lemma 5.1 If V (G ) can be covered by k disjoint cliques of size n 1 ≥ n 2 ≥ . . . ≥ n k , then ecc(G ) ≤ k + k i =1 (i -1)n i .
Proof We proceed by induction on k . The statement is trivial when k = 1, so assume that k > 1 and that the statement holds for all positive integers less than k . Let Q i be the clique of size n i in the vertex cover given by the statement of the theorem, and let

G = G -Q k . Since G can be covered by k -1 cliques, ecc(G ) ≤ k -1 + k -1 i =1 (i -1)n i .
We extend this clique cover as follows. First, for each q ∈ Q k and i ∈ {1, . . . , k -1}, add the clique q ∪ (N G (q ) ∩ Q i ). This adds (k -1)n k cliques which cover all edges with exactly one end in Q k . Adding the clique Q k gives our desired clique cover of size

k + k i =1 (i -1)n i .
A graph G is called tame if there exists a connected claw-free graph H with α(H ) ≥ 3 such that G is an induced subgraph of H . In [START_REF] Javadi | Edge clique cover of claw-free graphs[END_REF], it is shown that if G is a tame graph, then ecc(G ) ≤ n + 1, and further that ecc(G ) ≤ n if G is not the union of 3 cliques. They note, specifically, that graphs with independence number 2 which are the union of 3 cliques are tame. Lemma 5.1 gives a similar result for graphs which are the union of 3 cliques, with the requirement that G be tame omitted (in fact, no requirement on the independence number of the graph is imposed). We make use of this result in Section 5.3 for a specific class of graphs whose vertices can be covered by three cliques or, equivlantly, whose complement is 3-colourable.

Corollary 5.2 If χ(G ) can be properly 3-coloured with colour classes of size p ≥ q ≥ r , then ecc(G ) ≤ 2r + q + 3 and, in particular ecc(G ) ≤ n + 3.

Note that a further corollary to Corollary 5.2 is that if G is a minimal counterexample to Conjecture 1, then either χ(G ) ≥ 4 or every proper 3-colouring of G has colour classes of roughly equal size.

In light of the bound given in Corollary 2.6, we also note the following can be proven by a similar argument:

Corollary 5.3 If χ(G ) = 4, then ecc(G ) ≤ 3 2 n + 4.

| Fixed diameter

We show that any future work can be restricted to those graphs having diameter exactly 2.

Proposition 5.4

If G is a graph with α(G ) ≤ 2, then G has diameter at most 3.

Proof By contradiction, suppose that there is a vertex u and vertices v i , i = 1, 2, 3, 4 such that v i is at distance i from u.

The independent set u, v 2 , v 4 contradicts the assumption of α(G ) = 2.

Theorem 5.5 If G is a graph with α(G ) = 2 and diam(G ) = 3, then ecc(G ) ≤ n 2 + 1.
Proof Let u, v ∈ V (G ) be at distance 3. Let N i (u) denote the set of vertices at distance i from u in G . By Lemma 2.1, the sets N i (u) induce complete graphs for i = 1, 2, 3, since there are no edges between N i (u) and N i +2 (u) for i = 0, 1.

Further, the set = n 2 + 1. Note that n 2 + 1 ≤ n whenever n ≥ 2, and that this is the case in a graph of diameter 3.

N 2 (u) ∪ N 3 (u) induces a complete graph since if u 3 ∈ N 3 (u) and u 2 ∈ N 2 (u) are not adjacent, the set {u, u 2 , u 3 } is independent. Thus N 2 (u) ∪ N 3 (u)

| Forbidden induced subgraphs

Recall that a graph G is called H -free if no induced subgraph of G is isomorphic to H . In this section, we give bounds on ecc(G ) for a variety of H -free graphs, ultimately showing that Conjecture 1.1 holds when restricted to H -free graphs if

H is any graph on four vertices. To this end, we remind the reader of the graphs on four vertices which do not contain three independent vertices, given in Figure 1.

2K 2 P 4 co-claw C 4 paw diamond K 4 F I G U R E 1 4-vertex graphs with α ≤ 2 Proposition 5.6 If G is 2K 2 -free and α(G ) = 2, then ecc(G ) ≤ n.
Proof Let x and y be non-adjacent vertices. Since α(G ) = 2, {x, y } must dominate the graph. Let X = N (x ) \ N (y ), Y = N (y ) \ N (x ), and Z = N (x ) ∩ N (y ). By Theorem 4.9 and the observation at the end of Section 4 that the theorem applies to H -free graphs, we may assume that X and Y are non-empty. Since α(G ) = 2, each of X and Y is a clique; since Proof It is well known (see, e.g., [START_REF] Corneil | Complement reducible graphs[END_REF]) that any P 4 -free graph contains adjacent twins (that is, two vertices with identical closed neighbourhoods), and so the bound follows immediately from Lemma 4.2.

G is 2K 2 -free, X is complete to Y . Thus X ∪ Y is
Proposition 5.8 If G is co-claw-free and α(G ) = 2, then ecc(G ) ≤ n.

Proof

The assumptions on G imply that G is the disjoint union of isolated vertices, paths, and cycles of length at least 4.

If G has an isolated vertex, then G has a universal vertex and the result follows from Lemma 4.1.1. If some connected component of G is a path, then let x be an end of the path and y a neighbour; in this case, N G (y ) N G (x ), and the result follows from Proposition 4.3. The final case to consider is that G is a collection of disjoint cycles. It follows that χ(G ) ≤ 3, and G can be 3-coloured with colour classes of size p ≥ q ≥ r , where r equals the number of odd cycles in G . If 2r + q + 3 ≤ n, then ecc(G ) ≤ n by Lemma 5.2. Suppose that 2r + q + 3 > n. Since q ≤ 1 2 (nr ), it follows that 3r + 6 > n. Combining this bound with the fact that n ≥ 5r , we have that n < 15 and so r < 3. If r = 2, then G must be the disjoint union of two 5-cycles. If r = 1, then n ≤ 8 and G is a 5-cycle or 7-cycle, and if r = 0 then G is a 4-cycle. It is easy to check that each of these three graphs satisfy ecc(G ) ≤ n, completing the proof.

Rather than considering the cases of C 4 , the paw, and the diamond separately, we prove a stronger result on P 2 ∪ P 3 -free graphs (where P 2 ∪ P 3 denotes the complement of the disjoint union of a 2-vertex path and a 3-vertex path), noting that P 2 ∪ P 3 contains each of C 4 , the paw, and the diamond as an induced subgraph.

F I G U R E 2 P 2 ∪ P 3 Theorem 5.9 If G is P 2 ∪ P 3 -free and α(G ) = 2, then ecc(G ) ≤ n.

Proof Let G be a minimal counterexample. As mentioned at the end of Section 4, Theorem 4.9 holds when restricted to H -free graphs; for the rest of this proof we let H = P 2 ∪ P 3 . In particular, we may assume that G has no universal vertex, and that G contains no pair of vertices u, v such that

N (u) ⊆ N (v ) or N [u] ⊆ N [v ].
We may also assume, by It is easy to see that because the graph is H -free, every vertex in X has at most one neighbour in Y and vice versa.

Moreover if a vertex u ∈ X has no neighbour in Y then N [u] ⊆ N [x ]
, a contradiction. Thus, X and Y have same order and the edges between X and Y form a perfect matching x 1 y 1 , x 2 y 2 , . . . , x p y p .

Let z be a vertex in Z . It is easy to see that if z is not adjacent to y i then it is not adjacent to x i , since the graph is H -free. Furthermore, z must be adjacent to every other x j and y j since α(G ) = 2. This implies that Z can be partitioned (Z 0 , Z 1 . . . Z p ), where Z 0 is the set of vertices in Z adjacent to every vertex in X ∪ Y and Z i the set of vertices in Z adjacent to every vertex in X ∪ Y except x i and y i . Note, moreover, that for every i ≥ 1, Z i is a clique since α(G ) = 2 and x i is a non neighbour of the vertices in Z i . Figure 3 represents the graph at this point of the proof; we proceed by cases on possible values of p.

1 x 2 x 3 x p y 1 y 2 y 3 y p x y X Y Z 1 Z 2 Z 3 Z p Z 0 Z F I G U R E 3
The structure of a minimal counterexample to Theorem 5.9.

Case 1: p ≥ 4

We claim that Z is a clique. Let i and j be distinct integers between 0 and p, and let r , s be distinct integers in {1, . . . , p } \ {i , j }. The vertices {x, y r , x s } induce a P 3 which dominates Z i ∪ Z j , and so Z i ∪ Z j is a clique, and thus so is Z . We may then cover the edges of G with all cliques of the form{x i , y i } ∪ Z \ Z i together with the three cliques {x, y } ∪ Z , {x } ∪ X and {y } ∪ Y .

Case 2: p = 3

Let i be an integer between 1 and p, and let r , s be distinct integers in {1, . . . , p } \ {i }. The vertices {x, y r , x s } induce a P 3 which dominates Z i ∪ Z 0 , and so (as in Case 1), Z i ∪ Z 0 is a clique. In particular, if Z 0 is non-empty, then each element of Z 0 is a universal vertex in G , a contradiction. Thus, we may assume that Z 0 = ∅.

Let t = n -8 be the number of vertices in Z . If G [Z ] has no isolated vertex, then it is possible to cover all the edges of G [Z ] with t cliques by induction. We add the edge x y to every clique to get a family of t cliques that cover all edges within the graph induced by Z ∪ {x, y }. On the other hand, if Z has an isolated vertex u, then it has exactly one since α(G ) = 2. We can then cover the edges of G [Z ] by t -1 cliques by induction, add the edge x y to each of those cliques, and add the triangle x y u to get a family of t cliques that cover all edges within the graph induced by Z ∪ {x, y }.

We finally add the two cliques {x } ∪ X and {y } ∪ Y and the following six cliques to obtain our desired edge cover: as G is H -free. In other words, Z 0 must be a clique minus a matching. In particular, Z 0 is the union of two cliques A and B. Now we add the cliques A ∪ {x x 1 }, A ∪ {y y 1 }, B ∪ {x 1 y 1 } B ∪ {x y } to obtain the desired edge cover.

{x 1 , y 1 } ∪ Z 2 , {x 1 , y 1 } ∪ Z 3 , {x 2 , y 2 } ∪ Z 1 , {x 2 , y 2 } ∪ Z 3 , {x 3 , y 3 } ∪ Z 1 , {x 3 , y 3 } ∪ Z 2 .
Case 5: p = 0

In this case, x and y are universal vertices, a contradiction.

Finally, we note that any K 4 -free graph with α(G ) = 2 has at most 8 vertices, as R (3, 4) = 9. It is easily checked that these graphs, presented as their graph6 strings in Figure 4 (see [START_REF] Mckay | Ramsey Graphs[END_REF] for their complements), satisfy Conjecture 1. The results of this section imply the following:

Theorem 5.10 Let G be a graph with α(G ) = 2, and let H be any graph on four vertices. If G is H -free, then ecc(G ) ≤ n.

| Graph joins

Let G and G be two graphs. the complete join of G and G , denoted G ∨ G is the graph obtained by taking the disjoint union of G and G and adding all edges in between the two.

It is clear that α(G ∨ G ) = max(α(G ), α(G )) and in particular α(G ∨ G ) = 2 if α(G ) = α(G ) = 2. Therefore, in view of the conjectures examined here, one natural question is to ask whether ecc(G ∨ G ) ≤ ecc(G ) + ecc(G ).

The following theorem answers when G is a particular graph. If H is a spanning subgraph of H , then we say that H is a spanning supergraph of H . Proof Let x 1 , x 2 , . . . x n be the vertices of G such that x 1 , .., x k are the vertices of H in G . Let x 1 , . . . , x k the vertices of H labeled such that x i x j ∈ E (H ) → x i x j ∈ E (H ). Let K 1 , . . . K p be an optimal edge covering set of cliques for G. For i = 1 . . . p , consider the following set of vertices in G ∨ H :

K i = K i ∪ {x j such that x j ∈ K i }.
Similarly for i = 1 . . . k define

K i = {x i } ∪ (G \ N [x i ]
) ∪ {x j such that x i x j ∈ E (H ) and x i x j E (H )}

Lemma 2 . 1

 21 If α(G ) ≤ 2 and x is a vertex of G , N (x ) induces a clique in G .

Corollary 2 . 5

 25 As a consequence of Lemma 2.3, every edge of D is a dominating edge in G . By minimality, no edge remaining in G is a dominating edge of G . By Lemma 2.2, G has an edge clique cover C of size at most n. Since the only edges of G which are not covered by C are those in D , we are left to find a set of at most β (G D ) cliques which cover D in G . Let v ∈ V (G ) be any vertex and denote by D v = {vu 1 , . . . , vu k } the edges of D incident to v . Since u 1 , . . . , u k are nonneighbors of v in G , they form a clique in G by Lemma 2.2, and thus form a clique in G as well. Let K v = {v , u 1 , . . . , u k }; clearly K v covers D v . If W is a vertex cover for G D , then every edge of D is incident to some vertex w ∈ W . It then follows that {K w : w ∈ W } covers D , and so D can be covered by at most β (G D ) cliques as desired. If G is a graph with α(G ) = 2, then ecc(G ) ≤ n + δ(G ).Proof Let G , D , and G D be as in the proof of Theorem 2.4. Recalling that every edge in D is a dominating edge in G , it follows that, for any vertex

  It may seem tempting to consider this as evidence in favour of the validity of Conjecture 1, as graphs with low packing number might seem to be easier to cover with few cliques. However, ecc(G ) can be much greater than pack(G ) -the complete multipartite graph K 2,2,...,2 with n parts satisfies α(G ) = 2, pack(G ) = 4, and ecc(G ) = θ(log n) for large enough n[START_REF] Scheinerman | On the Fractional Intersection Number of a Graph[END_REF].

1 2Proposition 4 . 2 Proposition 4 . 3 Proposition 4 . 4

 1424344 and ecc(G [N (u)]) ≤ d (u) where u is a vertex of minimum degree. Proof The proofs of the first two claims are left to the reader. To prove the third, let C be a minimal clique cover of G [N (u)] for some vertex u satisfying the given condition. By adding u to each C ∈ C, we obtain a collection of cliques which covers all edges in G [N [u]]. By Proposition 2.1, N (u) is a clique, and so we are left only to cover those edges from N (u) to N (u). To do this, for each x ∈ N (u) we add the clique {x } ∪ (N (x ) ∩ N (u)). Altogether we have at most ecc(G [N (u)]) + d (u) + 1 cliques, as claimed. The fourth claim follows from the third, and the fifth from the fourth. Let G be a graph with α(G ) = 2. If G contains distinct vertices x, y ∈ V (G ) such that N [x ] ⊆ N [y ], then ecc(G ) ≤ ecc(Gy ) + 1.Proof If there exists such x and y , note that Z = N (y ) \ N (x ) is a clique. The family of at most ecc(Gy ) cliques covering the edges of Gy can easily be extended to the desired collection of ecc(Gy ) + 1 cliques by adding y to every clique that contains x , and adding a new clique {y } ∪ Z to the collection. Let G be a graph with α(G) = 2. If G contains non-adjacent vertices x, y ∈ V (G ) such that N (x ) N (y ) and ecc(Gy ) ≤ n -1, then ecc(G ) ≤ n.Proof Since α(G ) = 2 and x and y are non adjacent, every other vertex is adjacent to either x or y . Since N (x ) ⊆ N (y ), this gives that V (G ) = {x, y } ∪ N (y ). Note also that if there is an isolated vertex in the graph induced by N (y ), then N (y ) is just a clique plus an isolated vertex. With the addition of x and y , G can be edge covered with four cliques. Since we may easily assume that G has at least 4 vertices, we need only consider the case when every vertex in N (y ) has a neighbor in N (y ).Let A = N (y ) \ N (x ), which is non-empty by assumption. Denote by B the set of vertices in N (x ) which have a neighbor in A, and let C = N (x ) \ B. Since A is non-empty and α(G ) = 2, C is a clique. Let C 1 , C 2 , ...C p , with p ≤ n -1, be the collection of cliques which covers all edges of G \ y . For every i such that C i does not contain x , we add y to the clique C i (it is still a clique since y dominates every vertex but x ). We also add a new clique {y } ∪ C . We claim that this collection of at most n cliques is an edge cover of G . Every vertex a in A is adjacent to some edge in N (y ), so it must be contained in some clique C i that cannot contain x (since x and a are not adjacent), and therefore the edge y a will be covered by the new clique C i ∪ {y }. Every vertex b ∈ B is adjacent to some vertex a in A so the edge ab must be contained in some clique that cannot contain x , so similarly the new clique with y will contain the edge y b. Since we added the clique {y } ∪ C the collection is an edge cover as claimed. Let G be a graph with α(G ) = 2. If G contains non-adjacent vertices x, y such that N (x ) = N (y ) and ecc(G -{x, y }) ≤ n -2, then ecc(G ) ≤ n.Proof As in the proof of Proposition 4.3, V (G ) = {x, y } ∪ N (y ) and we may assume that every vertex in N (y ) has a neighbor in N (y ). Let G be the graph induced by N (y ). If G is complete then G satisfies the theorem. Assume then that x and y are non adjacent vertices in G . Now apply induction to G and get a family of cliques C 1 , C 2 , ...C p , with p ≤ n -2 that cover all edges of G . We add x to every clique that contains x , and y to every clique that contains y (note that no clique contain both x and y ). Denote by X (resp. Y ) be the set of neighbors of x (resp. y ) in G . Because α(G ) = 2, X \ Y and Y \ X induce cliques. It is easy to check that adding the cliques {x } ∪ (Y \ X ) and {y } ∪ (X \ Y )

  are cliques in G . By assumption, n uv cliques cover G [N uv ]. Consider the remaining edges to be coverered -(N u , N v ), (N u , N uv ), (N v , N uv ), (N uv , {u, v }) -where (A, B) denotes the set of edges between two sets A, B ⊂ V (G ). Let C y x denote the clique induced by {x, y } ∪ (N (x ) ∩ N y ), where x ∈ N uv , y ∈ {u, v }. There are n uv such cliques for each of y = u and y = v , and the collection of these cliques cover the edges (N u , N uv ), (N v , N uv ), and (N uv , {u, v }).

2 2

 2 and N [u] are two cliques which cover all edges of G except those having one end in N 1 (u) and the other in N 2 (u). Let A be the smaller of N 1 (u), N 2 (u) and let B be the other. Clearly |A | ≤ n-and the cliques C x induced by {x } ∪ (N (x ) ∩ B) for x ∈ A cover the remaining edges. Thus E (G ) is covered by at most 2 + n-2 2

Proposition 5 . 7

 57 a clique. Let n denote the order of G -{x, y } -X -Y . By induction, ecc(G -{x, y } -X -Y ) ≤ n . The remaining edges may be covered by the cliques x ∪ X , y ∪ Y , and X ∪ Y , and so the edges of G may be covered by at most n + 3 < n cliques. If G is P 4 -free and α(G ) = 2, then ecc(G ) ≤ n.

Lemma 2 . 2 ,

 22 that G has a dominating edge x y . Let us denote by X ,Y , Z the sets X = N (x ) \ N (y ), Y = N (y ) \ N (x ), and Z = N (x ) ∩ N (y ). Note that X and Y are cliques.

  x

Case 3 : p = 2 Case 4 : p = 1

 3241 By a similar argument as in Case 2, we use the P 3 induced by {x, y 1 , x 2 } to deduce that Z 0 is a clique. Also by a similar argument to that in Case 2, it is possible to cover the edges of G [Z ∪ {x, y }] with t = |Z | = n -6 cliques. We add the two cliques {x } ∪ X and {y } ∪ Y and the following four cliques to obtain our desired edge cover:{x 1 , y 1 } ∪ Z 0 , {x 1 , y 1 } ∪ Z 2 , {x 2 , y 2 } ∪ Z 0 , {x 2 , y 2 } ∪ Z 1 .Again, we apply an inductive argument to get a family of cliques of size |Z | = n -4 which covers all edges of G [Z ∪ {x, y }]. Now, since x and y 1 are non-adjacent vertices which are complete to Z 0 , there can be no P 3 in the complement of G [Z 0 ]

4

 4 The graph6 strings of those graphs satisfying ω ≤ 3 and α ≤ 2.

Theorem 5 .

 5 11 Let G be a graph such that α(G ) = 2. If H is an induced subgraph of G and H is any spanning supergraph of H , then ecc(G ∨ H ) ≤ ecc(G ) + |V (H ) |

  have exactly 2 connected components (call them A and B) and each much be a complete graph. Let X = {x 1 . . . ,x k }, let A i = G [x i ∪ (N (x i ) ∩V (A))], and let B i = G [x i ∪ (N (x i ) ∩V (B))].The collection of A i 's and B i 's are complete graphs which cover all edges from X to A ∪ B. By assumption, the edges of G [X ] can be covered by at most k complete subgraphs. Finally, we must cover A and B. Note that if x 1 is nonadjacent to a vertex in B, then it must be complete to A (and vice versa). Thus, either A or B (possibly both) has already been covered, and at most one more complete subgraph is needed. Thus E (G ) can be covered by 3k + 1 ≤ n complete subgraphs.

	Lemma 4.6 implies that any minimal counterexample to Conjecture 1 must have large connectivity. The following
	lemma implies that in any minimal counterexample, if it exists, any two non-adjacent vertices must have a large common
	neighbourhood, and the one following it shows that the connectivity bound can be improved if one considers only
	connected separators.

Lemma 4.7 Let G be a graph with α(G ) = 2 and let u, v ∈ V (G ) be a pair of non-adjacent vertices. If ecc

We note that an upper bound of

2(1o(1))n is cited in[START_REF] Javadi | Edge clique cover of claw-free graphs[END_REF], which is claimed to have been shown in a manuscript written by one of the authors of that paper.However, this manuscript does not appear to be available in publication and no explicit proof is given elsewhere.

We show that K i is a clique. By Lemma 2.1, (G \N [x i ]) induces a clique. Also, {x i }∪ {x j such that x i x j ∈ E (H ) and x i x j E (H )} induces a clique, because if for some j 1 and j 2 , x j 1 and x j 2 are non-neighbors, then x i , x j 1 and x j 2 form an independent set in H , a contradiction. Hence, K i is a clique. This gives (p + k ) cliques which cover all edges of G ∨ H .

| CONCLUSION

In this work we studied a conjecture that, if α(G ) = 2, then the edge clique cover number of G is at most |V (G ) | = n. We have provided the first known linear bound of 2nθ( n log n), and showed that under additional structural conditions the conjecture holds. However, a deeper look into our proof of Theorem 2.4 suggests that perhaps the upper bound provided by this theorem is nearly tight. The linear bound given in Corollary 2.6 relies on the lower bound for the Ramsey number R (3, t ), which is known to be tight (ignoring smaller order terms). By taking the complement of a graph which attains this bound, we have a graph G with α(G ) = 2 and lowest possible clique number. By adding a linear number of dominating edges, one may hope to construct an example where the proof technique of Theorem 2.4 is the optimal way of finding an edge clique cover. Currently, the only known technique for the construction of such ingredient graphs is the random triangle-free process given by Kim [START_REF] Kim | The Ramsey number R (3, t ) has order of magnitude t 2 /log t[END_REF]. The exploration of the details of this technique and its applications to Conjecture 1 is left as an open direction for future research.

| ACKNOWLEDGEMENTS

Manuel Lafond acknowledges financial support from the Natural Sciences and Engineering Research Council (NSERC).

Ben Seamone acknowledges financial support received from the Fonds de recherche du Québec -Nature et technologies.

This work was also partially supported by the ANR project HOSIGRA (ANR-17-CE40-0022).

R E F E R E N C E S