Jing Kong

Yaokun Wu
email: ykwu@sjtu.edu.cn.

On economical set representations of graphs †

Keywords: chordal graph, diamond-free elimination graph, edge clique graph, fractional intersection number, Helly property, intersection graph, intersection number, purple graph, maximal clique, maximal clique irreducible graph, ST weighting algorithm, unique representability

In this paper we discuss the bounds of and relations among various kinds of intersection numbers of graphs. Especially, we address extremal graphs with respect to the established bounds. The uniqueness of the minimum-size intersection representations for some graphs is also studied. In the course of this work, we introduce a superclass of chordal graphs, defined in terms of a generalization of simplicial vertex and perfect elimination ordering.

Introduction

We consider only finite undirected graphs without parallel edges or self-loops. Let G be a graph. A clique of G is one of its complete subgraphs. A clique is trivial provided it has no edges. A maximal clique is a clique which is not contained in any other one. We denote by C G the set of all cliques of G and by C(G) the set of all maximal cliques of G. For S ⊆ V (G), let G[S] denote the subgraph of G induced by S. When S = ∅, we often regard G[S] as a really trivial clique which has neither edges nor vertices.

Let S be a collection of sets. We say that G is the intersection graph of S if there is a mapping f from V (G) to S such that any two different vertices u, v ∈ V (G) are adjacent in G if and only if f (u) and f (v) have a nonempty intersection [START_REF] Erdős | The representation of a graph by set intersections[END_REF][START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] West | Introduction to Graph Theory[END_REF]. We call f a multifamily representation of G and say that f (v) represents v for each v ∈ V (G) in the representation. Sometimes, a multifamily representation is also referred to as an intersection representation or a set representation. The underlying set of the representation f is v∈V (G) f (v) and the size of f is defined to be the size of its underlying set. The intersection number of a graph G is the minimum size of a multifamily representation of G, denoted i(G). Note that intersection number is a function which is additive on the connected components of a graph. The study of intersection numbers plays a major part in various researches and has thus attracted much attention [START_REF] Chen | Clique covering the edges of a locally cobipartite graph[END_REF][START_REF] Cho | On the graph inequality θ E (G) ≥ θ E (G m )[END_REF][START_REF] Chung | The p-intersection number of a complete bipartite graph and orthogonal double coverings of a clique[END_REF][START_REF] Davi | The intersection number of an infinite graph[END_REF][START_REF] Il | Graphs satisfying inequality θ(G 2 ) ≤ θ(G)[END_REF][START_REF] Körner | Intersection number and capacities of graphs[END_REF][START_REF] Mahadev | On uniquely intersectable graphs[END_REF][START_REF] Michael | Sphericity, cubicity, and edge clique covers of graphs[END_REF][START_REF] Parthasarathy | The intersection number of K 4 -free graphs, Colloque sur la Théorie des Graphes[END_REF][START_REF] Raychaudhuri | Intersection number and edge clique graphs of chordal and strongly chordal graphs[END_REF][START_REF] Scheinerman | On the fractional intersection number of a graph[END_REF][START_REF] Tsuchiya | On intersection numbers, total clique covers and regular graphs[END_REF][START_REF] Tsuchiya | On uniform intersection numbers[END_REF][START_REF] Tsuchiya | On antichain intersection numbers, total clique covers and regular graphs[END_REF][START_REF] Wu | Poset, competition numbers, and interval graph[END_REF][START_REF] Salvi | The intersection number and point-distinguishing chromatic index of a graph[END_REF]. We mention especially that competition number, an important graph parameter, is a close variant of the intersection number and many researches on it could be translated as researches on intersection number as well and vice versa [START_REF] Dutton | A characterization of competition graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] Wu | Poset, competition numbers, and interval graph[END_REF].

Our paper is devoted to the economical set representation problem, namely the problem of minimizing the size of some restricted set representations of a given graph. The background of this problem can be illustrated as follows. On the one hand, as in many branches of mathematics, a useful approach to understand the structure of a graph is to study its representations, usually with some natural constraints. On the other hand, many practical problems can be formulated in terms of intersection models and thus reduce to solving some optimization problems on certain classes of intersection graphs. For some purposes, like storing a graph efficiently, we would like to determine how small the representations could be, how to identify such small representations, when they can be constructed efficiently and when the smallest representation is essentially unique. For more information on many related topics in intersection graph theory, we refer to [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] West | Introduction to Graph Theory[END_REF].

Let us identify various constraints for an intersection representation f. If f assigns distinct sets to different vertices of G, f is called a family representation of G. f is a Helly multifamily representation of G if f satisfies the Helly property [START_REF] Dourado | Complexity aspects of the Helly property: Graphs and hypergraphs[END_REF], namely for any clique K of G, it holds v∈V (K) f (v) = ∅. A family representation which satisfies the Helly property is named a Helly family representation. It is not hard to realize that each graph G possesses intersection representations which are family representations, multifamily representations, Helly multifamily representations, or Helly family representations, respectively. A good explanation of this fact can be found in Section 1.3 and Section 1.4 of [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]. We note that Gavril [START_REF] Gavril | Intersection graphs of Helly families of subtrees[END_REF] shows that every graph G is the intersection graph of a Helly multifamily of subtrees of a graph without triangles, namely it has a very special Helly multifamily representation.

We use family intersection number, Helly multifamily intersection number and Helly family intersection number, denoted i * (G), i h (G) and i * h (G), respectively, to be the minimum sizes of family representations, Helly multifamily representations and Helly family representations of G.

Lemma 1.1 (Erdős, Goodman, and Pósa [START_REF] Erdős | The representation of a graph by set intersections[END_REF]) [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]Theorem 1.6] The intersection number of a graph G is exactly the minimum number of cliques covering the edges of G.

In view of Lemma 1.1, for any graph G, i(G) turns out to be the solution α I (G) to the following integer linear programming problem.

Covering Problem I (CPI)

Minimize:

C∈C G w(C)
Subject To: e∈E(C),C∈C G w(C) ≥ 1 for each e ∈ E(G)

With: w(C) ∈ {0, 1} for each C ∈ C G .
CPI can be relaxed to a linear programming problem without the integral constraints as follows.

Covering Problem II (CPII)

Minimize:

C∈C G w(C) Subject To: e∈E(C),C∈C G w(C) ≥ 1 for each e ∈ E(G) With: w(C) ≥ 0 for each C ∈ C G .
Let α II (G) stand for the solution to CPII. Scheinerman and Trenk [START_REF] Scheinerman | On the fractional intersection number of a graph[END_REF] define α II (G) to be the fractional intersection number of a graph G, written as i f (G). It is immediate that

i(G) = α I (G) ≥ α II (G) = i f (G). (1)
We know that the determination of i(G) is NP-hard in general [START_REF] Kou | Covering edges by clique with regard to keyword conflicts and intersection graphs[END_REF]. But there are efficient algorithms to solve a linear programming problem and hence i f (G) serves as a computable lower bound for i(G) when we have all the necessary clique information as input to CPII. It is noteworthy that the number of maximal cliques might be exponential in terms of |V | + |E| and to report all these cliques is an important and difficult problem in combinatorial optimization [START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF].

Recall that a chordal graph is a graph with no induced cycles of length at least four [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] West | Introduction to Graph Theory[END_REF]. For any given chordal graph G, Scheinerman and Trenk [START_REF] Scheinerman | On the fractional intersection number of a graph[END_REF] present a weighting algorithm, which assigns {0, 1} weights to E(G) ∪ C G . They show that via this algorithm they can get a number which must be equal to both i(G) and i f (G), thus yielding the following theorem.

Theorem 1.2 (Scheinerman and Trenk

) [44, Theorem 5] If G is a chordal graph, then i(G) = i f (G).
Given an intersection representation f of G and any A ⊆ V (G), we write f (A) for v∈A f (v) and f (A) for v∈A f (v), respectively. Two intersection representations f 1 and f 2 of G will be regarded as the same provided there is a bijection

π from f 1 (V (G)) to f 2 (V (G)) such that π • f 1 = f 2 .
A graph G is said to be uniquely (intersection) representable with respect to family representation (ui) if it has only one family representation f satisfying |f (V (G))| = i * (G). Analogously, we can define uniquely representable with respect to multifamily representation (uim), uniquely representable with respect to Helly multifamily representation (uimh) and uniquely representable with respect to Helly family representation (uih), respectively. We note that characterizing uniquely representable graphs or/and giving a recognition algorithm has been pointed out by Golumbic as the first research problem in his book [26, p. 20].

Here is a very basic result on the uniqueness of minimum-size family intersection representation.

Theorem 1.3 (Alter and Wang [2]) [31, p. 156] Complete graphs with more than one vertex are not uniquely representable with respect to family representation.

The set consisting of all the vertices adjacent to a vertex v in G is referred to as the open neighborhood of it in G and denoted by N G (v), or merely N (v) if no confusion can arise. We say that two vertices u and v are twins if uv ∈ E(G) and N (v) = N (u), and in such a case we write uRv. Clearly, R is an equivalence relation on V (G). Each R-equivalence class is called a twin set. A graph is said to be twin-free provided each twin set consists of only one vertex. The graph obtained by deleting an edge from K 4 as shown in Fig. 1 is called a diamond.

Mahadev and Wang [START_REF] Mahadev | On uniquely intersectable graphs[END_REF] study among diamond-free graphs the unique representability problem. Note that in their study of intersection representations, they require that no empty set can be used to represent a vertex. But it is easy to check that their result below also holds in our current framework. (ii) G is twin-free; (iii) The intersection number and the fractional intersection number of G are equal.

The rest of this paper is organized as follows. The next section, Section 2, makes some elementary observations on the Helly multifamily intersection numbers. In Section 3, we put forward a sufficient condition for the validity of i(G) = i f (G), which will play a key role in this work. Then we move on in the subsequent two sections to further explore some graph classes satisfying i(G) = i f (G) by making use of this general criterion. In Section 4, as a direct generalization of Theorem 1.2, we discuss those graphs whose edge clique graphs are perfect; particularly, the so-called diamond-free elimination graphs are introduced there as a generalization of chordal graphs and are shown to satisfy i(G) = i f (G). In Section 5, we address the so-called maximal clique irreducible graphs, which turn out to be those graphs with i(G) = i f (G) = i h (G); in particular, we identify a hierarchy of subclasses of maximal clique irreducible graphs, each of them is characterized by having some special intersection representations. Subsequently, in Section 6 we present a greedy algorithm to generate a set representation for any given graph. We take a closer look at the diamond-free elimination graphs and show that there is a polynomial time recognition algorithm for them and the greedy algorithm can be used to produce a minimum-size intersection representation for them in polynomial time. In Section 7 we are concerned with various lower bounds for i * (G) and i * h (G) and extremal graphs with respect to these parameters. We define a purple graph to be a sort of extremal graphs with respect to the Helly family intersection number. Then Section 8 is devoted to some intersection representation problems for purple graphs, including a generalization of the (ii) ⇔ (iii) part of Theorem 1.4. Finally, we discuss in Section 9 the uniqueness of economical set representations and obtain generalizations of Theorem 1.3 as well as the (i) ⇔ (iii) and the (i) ⇔ (ii) parts of Theorem 1.4.

Helly multifamily intersection number

It is straightforward from the definitions that

i(G) ≤ i h (G) ≤ i * h (G); i(G) ≤ i * (G) ≤ i * h (G). (2)
To say more about the relationship among these intersection numbers, we examine some basic facts about the Helly multifamily intersection number.

For each set representation

f of G, let ξ(f ) = {G[V x ] : x ∈ f (V (G))}, where V x = {v : x ∈ f (v)} for each x ∈ f (V (G)).
Theorem 2.1 (Roberts and Spencer [START_REF] Roberts | A characterization of clique graphs[END_REF]) [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]Lemma 1.11] An intersection representation f of a graph G satisfies the Helly property if and only if C(G) ⊆ ξ(f ). Example 2.3 For the graphs G and H in Fig. 2,

(v) = {C ∈ C(G) : v ∈ V (C)} for each v ∈ V (G). But Theorem 2.1 implies that |C(G)| ≤ i h (G).
{f (a) = {1}, f (b) = {1, 2}, f (c) = {1, 3}, f (d) = {3}, f (e) = {2, 3}, f (g) = {2}} and {f ′ (a) = {2, 3}, f ′ (b) = {1, 3}, f ′ (c) = {1, 2}, f ′ (d) = {1, 2, 3}, f ′ (e) = {1}}
give minimum-size family intersection representations of them, respectively. By Lemma 2.2, for the graph G we have i h (G) = 4 > 3 = i * (G); while for the graph H we have i h (H) = 2 < 3 = i * (H).

Erdős, Goodman and Pósa [START_REF] Erdős | The representation of a graph by set intersections[END_REF]

establish that i(G) ≤ ⌊ |V (G)| 2 4
⌋. But i h (G) can be exponentially large, as can be seen from the forthcoming example, which then tells us that i h (G) can be much larger than i(G).

Example 2.4 [START_REF] Miller | A problem of maximum consistent subsets[END_REF][START_REF] Moon | On cliques in graphs[END_REF] Let n ≥ 2 and G be a graph with n vertices. Then we have

|C(G)| ≤    3 n/3 , if n ≡ 0 ( mod 3); 4 × 3 ⌊n/3⌋-1 , if n ≡ 1 ( mod 3); 2 × 3 ⌊n/3⌋ , if n ≡ 2 ( mod 3). (3)
Equality in (3) holds if and only if V (G) can be partitioned into disjoint subsets where each of them has three vertices with at most either one exception which has two or four vertices or two exceptions which both have two vertices and any two vertices are joined by an edge if and only if they come from different subsets.

For some classes of graphs we have more knowledge of their clique distributions and hence can get some better upper bounds for i h (G). For example, we can deduce from the existence of a perfect elimination ordering [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Dirac | On rigid circuit graphs[END_REF][START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] Rose | Triangulated graphs and the elimination process[END_REF] that a chordal graph G has at most |V (G)| maximal cliques. We also know that a graph of boxicity k has at most O(|V (G)| k ) maximal cliques [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Roberts | On the boxicity and cubicity of a graph[END_REF]. We mention that to detect/enumerate the maximal cliques of various graph classes is a problem arising in many important applications [START_REF] Butenko | Clique-detection models in computational biochemistry and genomics[END_REF].

Main result

Following Theorem 1.2, we will develop a more general sufficient condition for a graph to have equal fractional intersection number and intersection number.

First we need to introduce some more concepts. The independence number α(G) of a graph G is the maximum size of an independent set of G. The minimum number of cliques in G needed to cover V (G) is referred to be its clique cover number and denoted by θ(G). The edge clique graph of a graph G, denoted K e (G), is the one whose vertices are the edges of G and two vertices are adjacent if and only if when regarded as edges of G they belong to a clique of G [START_REF] Albertson | Duality and perfection for edges in cliques[END_REF][START_REF] Cerioli | A characterization of edge clique graphs[END_REF][START_REF] Cerioli | Edge clique graphs and some classes of chordal graphs[END_REF][START_REF] Chartrand | Edge-clique graphs[END_REF][START_REF] Kou | Covering edges by clique with regard to keyword conflicts and intersection graphs[END_REF][START_REF] Raychaudhuri | Intersection number and edge clique graphs of chordal and strongly chordal graphs[END_REF][START_REF] Raychaudhuri | Edge clique graphs of some important classes of graphs[END_REF].

Next we present our main result, which confirms that edge clique graph is a natural context in investigating intersection numbers. Note that both PPI and PPII are feasible and thus have optimal solutions, which we denote by β I (G) and β II (G), respectively. It follows at once that

Theorem 3.1 Let G be a graph. If θ(K e (G)) = α(K e (G)), then i(G) = i f (G).
β II (G) ≥ β I (G), (4)
as PPI becomes PPII after directly dropping the integral assumption. Invoking the Duality Theorem of Linear Programming [START_REF] Gale | Linear Programming and the Theory of Games[END_REF], we arrive at

α II (G) = β II (G). (5)
Putting together Eqs. ( 1), ( 4) and ( 5), we have

α I (G) ≥ α II (G) = β II (G) ≥ β I (G). (6)
Next, we consider the relationship between a graph and its edge clique graph. For any clique C of G, the edge set of C corresponds to the vertex set of a clique in K e (G), denoted by γ(C); conversely, for any clique C ′ of K e (G), the set of edges of G corresponding to vertices of C ′ must lie in the edge set of a clique of G and among all such cliques there is a unique minimal one, say γ ′ (C ′ ). The maps γ and γ ′ are order-preserving and induce a one-to-one correspondence between the cliques of K e (G) and those cliques C of G which satisfy C = γ ′ γ(C). In particular, this leads to the following result.

Lemma 3.2 (Albertson and Collins [1]) [10, Proposition 1] There exists a one-to-one correspondence between nontrivial maximal cliques (intersection of nontrivial maximal cliques) of G and maximal cliques (intersection of maximal cliques) of K e (G). Moreover, if C is a nontrivial maximal clique (intersection of maximal cliques) of G, then the corresponding clique of K e (G) is formed by the vertices which correspond to the edges of G with both endpoints in C.

Moreover, the correspondence between the cliques of G and K e (G) as described before implies the lemma below.

Lemma 3.3 θ(K e (G)) = α I (G) and α(K e (G)) = β I (G).
From here it is a short step to finishing the proof of Theorem 3.1. [START_REF] Raychaudhuri | Edge clique graphs of some important classes of graphs[END_REF] demonstrates that any four-wheel-free transitively orientable graph G satisfies θ(K e (G)) = α(K e (G)). Thus Theorem 3.1 immediately implies that any four-wheel-free transitively orientable graph

Proof of Theorem 3.1:

By Lemma 3.3, we deduce from θ(K e (G)) = α(K e (G)) that α I (G) = β I (G), which combined with inequality (6) leads to i(G) = α I (G) = α II (G) = i f (G), as claimed. ✷ Example 3.4 Raychaudhuri
G satisfies i(G) = i f (G).

Graphs whose edge clique graphs are perfect

We begin with an immediate corollary of Theorem 3.1.

Theorem 4.1 Each graph G whose edge clique graph is perfect satisfies

i(G) = i f (G).
In view of Theorem 4.1, it is of interest to investigate those graphs whose edge clique graphs are perfect. [START_REF] Albertson | Duality and perfection for edges in cliques[END_REF] show that if G is planar and 3-colorable, then K e (G) is perfect.

Example 4.2 Albertson and Collins

Example 4.3 It is known that the edge clique graph of a chordal graph is still chordal [START_REF] Albertson | Duality and perfection for edges in cliques[END_REF][START_REF] Raychaudhuri | Intersection number and edge clique graphs of chordal and strongly chordal graphs[END_REF][START_REF] Raychaudhuri | Edge clique graphs of some important classes of graphs[END_REF] and hence perfect. Note that this means that Theorem 4.1 is a generalization of Theorem 1.2.

Our remaining objective in this section is to generalize the observation made in Example 4.3. To this end, we need a bit more terminology.

We think of an ordering [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF][START_REF] Rose | Triangulated graphs and the elimination process[END_REF]. Generalizing the concept of chordal graphs, we define a diamond-free elimination graph to be a graph whose vertex set has a generalized perfect elimination ordering (gpeo), namely an ordering σ with the property that G

σ of V (G) as a bijection from V (G) to {1, 2, . . . , |V (G)|}. Put N (v, σ) = {u ∈ N (v) : σ(u) > σ(v)}. An ordering σ is a perfect elimination ordering (peo) if for each v ∈ V (G), N (v, σ) induces a clique of G. Recall that a graph is chordal if and only if it possesses a peo [5, Theorem 1.2.2] [17,
[N (v, σ)] is a vertex-disjoint union of cliques for each v ∈ V (G). It is easy to see that a diamond-free elimination graph G has at most |E(G)| maximal cliques.
A simple characterization of gpeo is as follows.

Lemma 4.4 An ordering σ of V (G) is a gpeo if and only if for each

v ∈ V (G) and each u ∈ N (v, σ), N (v, σ)∩N (u) induces a clique of G. In particular, if G has a gpeo and if there is v ∈ V (G) satisfying that N (v) ∩ N (u) induces a clique of G for each u ∈ N (v), then G -v also has a gpeo.
For any ordering σ of V (G), there is a unique ordering σ ′ of V (K e (G)) such that σ ′ (uv) < σ ′ (xy) if and only if either min(σ(u), σ(v)) < min(σ(x), σ(y)) or min(σ(u), σ(v)) = min(σ(x), σ(y)) but max(σ(u), σ(v)) < max(σ(x), σ(y)). It is not hard to see the following result which indicates the connection between chordal graphs and diamond-free elimination graphs. Lemma 4.5 σ is a gpeo of G if and only if σ ′ is a peo of K e (G). Hence the edge clique graph of a diamond-free elimination graph is chordal.

We are now ready to show that any diamond-free elimination graph G fulfils i(G) = i f (G). Note that we will show in Section 6 that a diamond-free elimination graph can be recognized in polynomial time and there is a greedy algorithm to determine its intersection number directly, rather than compute its fractional intersection number via solving a linear programming problem.

Theorem 4.6 If G is a diamond-free elimination graph, then i(G) = i f (G).
Proof: It is well-known that chordal graphs are perfect [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Lovász | Normal hypergraphs and the perfect graph conjecture[END_REF][START_REF] West | Introduction to Graph Theory[END_REF]. So, the result comes from Theorem 4. Example 4.8 The graph displayed in Fig. 3 is neither chordal nor diamond-free. But it has a gpeo as indicated in the figure and thus is a diamond-free elimination graph.

The following example says that the converse of the second part of Lemma 4.5 is not valid. Indeed, an edge clique graph K e (G) is chordal exactly means that it has a peo, say τ , and it may happen that there is no ordering σ of G such that τ = σ ′ . Example 4.9 Let G be the graph as depicted on the left of Fig. 4. Since N G (v) does not induce a vertexdisjoint union of cliques for any v ∈ V (G), G is not a diamond-free elimination graph. However, its edge clique graph, as exhibited on the right of Fig. 4, is a chordal graph. Example 5.1 For t ≥ 3, the Tsuchiya graph T 2t [START_REF] Tsuchiya | On antichain intersection numbers, total clique covers and regular graphs[END_REF] is specified by setting V (T 2t ) = {1, 2, . . . , 2t} and E(T 2t ) = {(i, i + 1), (t + i, t + i + 1), (i, i + t + 1), (i + 1, t + i), (i, i + t) : i ∈ Z t }. For any odd integer t ≥ 5, we take F t ⊆ V (K e (T 2t )) to be i∈Zt {(i, i + t)}. See Fig. 5 for an illustration of T 10 and F 5 . We can check that F t induces a chordless odd cycle of length at least 5 in K e (T 2t ) and hence K e (T 2t ) is not a perfect graph. This means that we cannot use Theorem 4.1 directly to tell whether or not the Tsuchiya graph T 2t has equal intersection number and fractional intersection number.

5 Graphs satisfying i(G) = i f (G) = i h (G)
Besides the work in Section 4, we will develop in this subsection another consequence of Theorem 3.1. Among many applications of this result, it will enable us to find out in the next subsection that the intersection number, the fractional intersection number and the Helly intersection number of any given Tsuchiya graph are all equal; see Corollary 5.8.

A special vertex of a graph G is a vertex which is contained in only one maximal clique of G and a special edge of G is one edge which only appears in one maximal clique of G. Wallis and Zhang [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] Wallis | On maximal clique irreducible graphs[END_REF] define a graph G to be maximal clique irreducible if each nontrivial maximal clique of G contains a special edge. We remark that G is maximal clique irreducible if and only if C(K e (G)) is an irreducible covering of K e (G) [START_REF] Tomescu | Irreducible coverings by cliques and Sperner's theorem[END_REF]. We are ready to present the main theorem of this subsection.

Theorem 5.2 If G is maximal clique irreducible, then i(G) = i f (G).
Proof: By means of Lemma 3.2, the cliques in C(K e (G)) are in one-to-one correspondence with the nontrivial cliques from C(G). Since every nontrivial clique in C(G) has a special edge, correspondingly, each member of C(K e (G)) contains a special vertex in K e (G). Taking from each clique in C(K e (G)) one special vertex we obtain an independent set of size |C(K e (G))| and thus α(K e (G)) ≥ |C(K e (G))| ≥ θ(K e (G)) follows. On the other hand, by the pigeon-hole principle we know that α(K e (G)) ≤ θ(K e (G)). The conjunction of these two inequalities then implies that θ(K e (G)) = α(K e (G)) an so we can apply Theorem 3.1 to get i(G) = i f (G). ✷

We proceed with an investigation of maximal clique irreducible graphs. As we shall see, this class of graphs is characterized by i(G) = i f (G). We will arrive at such a conclusion by taking things step by step.

As was observed in Eq. ( 2), we have i(G) ≤ i h (G) for any graph G. In this regard, the next lemma shows that maximal clique irreducible graphs are some sort of extremal graphs.

Lemma 5.3 G is maximal clique irreducible if and only if i(G) = i h (G).

Proof: We prove the backward direction by contradiction. Assume that there exists a clique C ∈ C(G) which has no special edge. This means that the union of cliques in C(G) \ {C} covers E(G). As a consequence of Lemmas 1.1 and 2.2, we then find that i(G) < |C(G)| = i h (G), contrary to our assumption. Now consider the forward direction. Let

C(G) = {Q 1 , . . . , Q |C(G)| }. For each nontrivial Q i ∈ C(G)
, let S i = ∅ be the set of its special edges. If there is a family of cliques of size less than |C(G)| whose union covers E(G), then we can find a clique in this family intersecting with at least two different S i 's, which is impossible.

✷ Theorem 5.4 If i(G) = i h (G), then i(G) = i f (G) = |C(G)|.
Proof: This is a consequence of Theorem 5.

if i(G) = i f (G) = i h (G) = |C(G)|.
Example 5.6 Each triangle-free graph is a diamond-free graph and each edge of a diamond-free graph is a special edge. Thus, Theorem 5.5 says that each triangle-free graph G, or more generally, each diamondfree graph G, satisfies i(G) = i h (G) = i f (G). This strengthens our former assertion in Example 4.7. ). An ordering π of C(G) is circular provided that the maximal cliques containing any given vertex appear in a circular consecutive order in π -imagine the ordering as wrapped around a circle. A Helly circular-arc graph is the one whose set of maximal cliques has a circular ordering [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Gavril | Algorithms on circular-arc graphs[END_REF][START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]. We denote the class of Helly circular-arc graphs by HCA. From this definition it is easy to see that the class of interval graphs belong to HCA [START_REF] Fulkerson | Incidence matrices and interval graphs[END_REF].

A hierarchy of maximal clique irreducible graphs

For any given graph we can recognize whether or not it belongs to HCA in polynomial time [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Gavril | Algorithms on circular-arc graphs[END_REF].

Corollary 5.7 If G ∈ HCA, then G is maximal clique irreducible and i(G) = i h (G) = i f (G). Proof: Let π = {C 1 , . . . , C |C(G)| } be a circular ordering of C(G). For each i ∈ Z |C(G)| , choose a vertex u i ∈ C i \ C i+1 and a vertex w i ∈ C i \ C i-
i(T 2t ) = i h (T 2t ) = i f (T 2t ).
To gain more understanding of the graphs satisfying i(G) = i h (G) = i f (G), namely maximal clique irreducible graphs, we proceed to discuss a hierarchy of some subclasses of them and provide characterizations of them from the viewpoint of intersection representations. The bottom of this hierarchy will be the class of Helly circular-arc graphs mentioned above and the top will be the class of maximal clique irreducible graphs.

A family F of sets is said to have the strong Helly property [START_REF] Bretto | A polynomial algorithm for the strong Helly property[END_REF] if for every pairwise intersecting subfamily F ′ ⊆ F there exist S 1 , S 2 ∈ F ′ such that S∈F ′ S = S 1 ∩ S 2 . Weakening slightly this definition, we assert that a family F of sets has the semistrong Helly property if for every maximal pairwise intersecting subfamily F ′ ⊆ F there exist S 1 , S 2 ∈ F ′ such that S∈F ′ S = S 1 ∩ S 2 . An intersection representation f where {f (v) : v ∈ V (G)} has the strong (semistrong) Helly property is called a strong (semistrong) Helly representation. We designate the class of graphs that have a strong Helly representation as SH and those having a semistrong Helly representation as SSH, respectively. We remark that a graph belongs to SH if and only if every induced subgraph of it belongs to SSH. It is also noteworthy that SH is nothing but the line graphs of strong Helly hypergraphs [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF].

Recall that maximal clique irreducible graphs are identified by a special property of their clique structure. In contrast, SSH is characterized by the possession of a special kind of set representations. We now show that they are merely the same object defined from different points of view. Theorem 5.9 SSH is exactly the class of maximal clique irreducible graphs. Hence, by Theorems 5.5, for any graph

G, i(G) = i h (G) = i f (G) if and only if G ∈ SSH.
Proof: First assume that G has a semistrong Helly representation f and take arbitrarily a nontrivial maximal clique C of G. It suffices to show that C has a special edge. The semistrong Helly property of f guarantees the existence of two vertices u, w ∈ V (C) such that f (V (C)) = f (u) ∩ f (w). We can assume u = w; otherwise we simply use any other vertex from V (C) \ {u} = ∅ to be the new w. We claim that the edge uw is a special edge. Actually, for any maximal clique C ′ which includes both u and w, we have

∅ = f (V (C ′ )) ⊆ f (u) ∩ f (w) = f (V (C)) and hence ∅ = f (V (C) ∪ V (C ′ )) follows. Since f is an intersection representation of G, we know that G[V (C) ∪ V (C ′ )
] must be a clique and then infer from the maximality of C and C ′ that C = C ′ . Of course, this means that uw is a special edge, as asserted.

For the reverse direction, assign to each

v ∈ V (G) the set f (v) = {C ∈ C(G) : v ∈ V (C)}. It is easy to verify that f is an intersection representation of G. Suppose that C ∈ C(G) is trivial, say C = {x}. Clearly, f (x) = {C}. Hence, taking u = w = x, we can write f (V (C)) = f (u) ∩ f (w).
We then take up the case that C ∈ C(G) is nontrivial. For now, C has a special edge, say uw, that is to say, f (u) ∩ f (w) = {C}. But for any v ∈ V (C) we surely have C ∈ f (v). This immediately leads to f (V (C)) = f (u) ∩ f (w) = {C}. Thus we have come to the conclusion that f is a semistrong Helly representation of G and the proof is done. ✷

It is obvious that SH ⊆ SSH. Currently, we are not aware of any existing interesting graph class which lies in SSH \ SH. Anyway, we do know that SH = SSH, as indicated by the example below.

, f (V (C)) = f (a) ∩ f (b), namely f (a) ∩ f (b) ⊆ f (c). But {d, a, b} is a clique and so ∅ = f (d) ∩ f (a) ∩ f (b) ⊆ f (d) ∩ f (c).

This is impossible as there is no edge in G connecting c and d.

A graph G is a hereditary clique-Helly graph if C(G) satisfies the strong Helly property [START_REF] Prisner | Hereditary clique-Helly graphs[END_REF][START_REF] Wallis | On maximal clique irreducible graphs[END_REF]. Following Prisner [START_REF] Prisner | Hereditary clique-Helly graphs[END_REF], we use the notation HCH for this class of graphs. We define the clique graph operator K(•) such that, for any graph H, K(H) is the intersection graph of the maximal cliques of H. A graph is a clique graph if it is isomorphic to K(H) for some graph H.

Two interesting results about HCH are as follows.

Lemma 5.11 (Prisner [37]) [32,

p. 129] A graph is a hereditary clique-Helly graph if and only if each of its vertex-induced subgraphs is maximal clique irreducible.

Lemma 5.12 (Prisner [START_REF] Prisner | Hereditary clique-Helly graphs[END_REF]) [START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]Theorem 7.34] A graph is a hereditary clique-Helly graph if and only if G = K(H) where H is another hereditary clique-Helly graph.

We are now prepared to show that HCH and SH are the same graph class.

Theorem 5.13 HCH = SH.

Proof: For any G ∈ HCH, by Lemma 5.12 we know that G is the clique graph of some hereditary clique-Helly graph H. According to the definition of a hereditary clique-Helly graph, C(H) is a family with the strong Helly property, thus implying G ∈ SH. This completes the proof of HCH ⊆ SH.

Conversely, suppose G is a member of SH and f is a strong Helly representation of G. We aim to deduce that G ∈ HCH from which the theorem then follows. By Lemma 5.11, it is enough to prove that each of its vertex-induced subgraphs G ′ is maximal clique irreducible. Let f | G ′ be the representation f restricted to V (G ′ ). Clearly, f | G ′ is an intersection representation of G ′ which satisfies the strong Helly property. By Theorem 5.9, we get that G ′ is maximal clique irreducible, as was to be shown.

✷

We now go back to HCA. We will show that HCA ⊆ HCH, thus strengthening Corollary 5.7. An equivalent definition of Helly circular-arc graph will be needed: A Helly circular-arc graph is the intersection graph of a Helly family of circular arcs on a circle [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Gavril | Algorithms on circular-arc graphs[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF]. We will also make use of a simple result which we single out as a lemma. A class of graphs is said to be induced-hereditary if each induced subgraph of a member of it also belongs to it [START_REF] Borowiecki | A survey of hereditary properties of graphs[END_REF]. It follows readily from the definition of HCA as described above that HCA is induced-hereditary.

Lemma 5.14 An induced-hereditary class of graphs belongs to HCH if and only if it is a subclass of SSH.

Proof: This is an application of the combination of Theorem 5.9 and Lemma 5.11. ✷ Theorem 5.15 HCA ⊆ HCH.

Proof: Corollary 5.7 combined with Theorem 5.9 asserts that HCA ⊆ SSH. Further applying Lemma 5.14 and our remark prior to it, this enables us to draw the conclusion, as required. ✷ Summing up what we have obtained in this subsection, we can state the following result.

Theorem 5.17 HCA HCH = SH SSH.

The ST weighting algorithm

In this section we will present a greedy algorithm for any given graph, which can output a set of cliques covering every edge of it. Surely, this then easily leads to a set representation of the graph and an upper bound of its intersection number. We will show that with the knowledge of a gpeo of a given diamond-free elimination graph, what comes out from this greedy algorithm is a minimum-size set representation.

Adapting the weighting algorithm of Scheinerman and Trenk [START_REF] Scheinerman | On the fractional intersection number of a graph[END_REF] as mentioned in Section 1, we give the following algorithm, which we call the ST weighting algorithm.

ST Weighting Algorithm: Input: A graph G and a vertex ordering σ of G. Initialize: Let w(C) = w(e) = 0 for every clique C and edge e of G. Mark all edges as "uncovered".

Set G 1 = G. For i = 1 to |V (G)| -1 do: (1) Let {C i,1 , . . . , C i,ki } = {C ∈ C(G i ) : σ -1 (i) ∈ V (C)}.
For j = 1 to k i do:

If there is an edge e of C i,j incident to σ -1 (i) that is marked "uncovered", then (a) Let w(C i,j ) = w(e) = 1.

(b) Mark all edges in C i,j " covered".

End of for loop

(2) Let G i+1 = G i -σ -1 (i).

End of for loop Output:

The weight function

w from E(G) ∪ C G to {0, 1}.
For convenience, the outer For loop in the ST weighting algorithm is called the ith pass. During the ith pass there are still k i inner For loops which we will call iterations. Notice that for i = 1, . . . , n -1, all edges incident to σ -1 (i) will be marked "covered" at the end of the ith pass. Hence all edges of G are marked by the ST weighting algorithm. Accordingly, for any given edge e, there are i and j such that e is marked by the operation (b) during the jth iteration of the ith pass. In the same iteration, the operation (a) then assigns weight 1 to a clique C satisfying e ∈ E(C). Since the weights given to cliques in C G are from {0, 1}, this verifies our statement.

Let Q σ be the set of cliques of G receiving weight 1 at the end of the ST weighting algorithm. Since C∈C G w(C) is a feasible solution to CPII, we get that the union of the cliques in Q σ covers E(G). It is now a simple and well-known procedure to yield the required intersection representation f of size

|Q σ | = C∈C G w(C): for each v ∈ V (G), let f (v) = {C ∈ Q σ : v ∈ V (C)}. ✷
Since we can find an intersection representation for any graph and any vertex ordering with the help of the ST weighting algorithm, it is natural to consider the following question.

Question 6.2 For any graph G and its vertex ordering σ, can we estimate the difference between i(G) and the size of the intersection representation obtained by the ST weighting algorithm? For which kind of graph classes can we have some ordering with which the ST weighting algorithm can produce a minimumsize set representation? How to search for such a good ordering efficiently? For which class of graphs can the ST weighting algorithm lead to an approximation algorithm for deciding the intersection number and what is its performance guarantee?

In Section 4 we have seen that any chordal graph is a diamond-free elimination graph. Indeed, to prove the next theorem we follow the idea of Scheinerman and Trenk [START_REF] Scheinerman | On the fractional intersection number of a graph[END_REF] in deducing Theorem 1.2. Theorem 6. 3 Let G be a diamond-free elimination graph and σ a generalized perfect elimination ordering of G. If w is the weight function arising from the ST weighting algorithm with σ as an input, we have

C∈C G w(C) = i(G) = i f (G).
Proof: It is sufficient to prove that C∈C G w(C) is the optimal solution to the linear program CPI.

First observe that each time we give a clique weight 1 in applying the ST weighting algorithm, we exactly assign one edge a weight 1. Thus we get that e∈E(G) w(e) and C∈C G w(C) are equal, say W.

We next intend to show that W is a feasible solution to the linear program PPII, i.e., e∈E(C) w(e) ≤ 1 for each C ∈ C G . Assume that there is at least one weight-1 edge in E(C). Since at each iteration, at most one edge is assigned weight 1, we can assume that at the jth iteration of the ith pass the first edge from E(C), say xy, receives weight 1. Since we only give weight 1 to edges incident to σ -1 (i) in the ith pass, we can further assume that x = σ -1 (i). Clearly, when the (i -1)th pass terminates, all edges in E(C) \ E(G i ) = {uv ∈ E(C) : min(σ(u), σ(v)) < i} have been marked "covered" and will keep a weight 0 from then on. The assumption that σ is a gpeo tells us that for each edge from E(C) ∩ E(G i ) there is a unique 1 ≤ j ≤ k i such that this edge lies in E(C i,j ), and the value j for this edge must be the same as for xy. Consequently, all edges e = xy of E(C) ∩ E(G i ) will be marked "covered" at the jth iteration of the ith pass and keep a weight 0 since then. This then proves that xy is the only edge of E(C) that receives a weight 1.

Finally, recall that in course of the proof of Lemma 6.1, we already show that W is a feasible solution to CPII.

Taking all things together, we know that W must be the optimal solution to CPII which then gives W = i f (G). Since the weight function only takes value from {0, 1}, W is also the optimal solution to the integer linear program CPI, from which W = i(G) follows. ✷ Lemma 6.1 in combination with Theorem 6.3 implies that, for any diamond-free elimination graph, if a gpeo is already known, we can produce an intersection representation of minimum size for the graph by running the ST weighting algorithm. But is it easy to tell whether or not a gpeo exists and construct a gpeo in the case that it exists? Again, we can devise a very naive way to do it: Search for a vertex v such that each set of the form N (u) ∩ N (v), u ∈ N (v), induces a clique of G; eliminate v and all the edges incident to it; repeat the same step on the remaining graph until no vertex remained can be removed; record the sequence of vertices being deleted in order. If the input graph has a gpeo, Lemma 4.4 guarantees that we will find one when the algorithm terminates; otherwise, the algorithm halts before we delete every vertex of the graph and we can assert that there is no gpeo for the graph. It is not hard to see that this gives a O(|V (G)| 5 ) time algorithm for the recognition of diamond-free elimination graphs. Note that there are linear time recognition algorithms for chordal graphs [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Mckee | Topics in Intersection Graph Theory[END_REF][START_REF] Rose | Algorithmic aspects of vertex elimination on graphs[END_REF][START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs and selectively reduce acyclic hypergraphs[END_REF][START_REF] West | Introduction to Graph Theory[END_REF] and there are good algorithms to enumerate all peos of a chordal graph [START_REF] Chandran | Fast generation of all perfect elimination orderings of a chordal graph[END_REF]. It will be interesting if those kind of work can be generalized to produce some clever algorithms for diamond-free elimination graphs.

We have shown how to find a gpeo for a diamond-free elimination graph G and how to generate a minimum-size intersection representation of G with the help of ST weighting algorithm. We claim that the whole process can be completed in polynomial time. Indeed, when implementing the ith pass of the ST weighing algorithm on G with one of its gpeo, say σ, as an input, we deal with the graph with vertex set {σ -1 (j) : j ≥ i} and edge set of uncovered edges then. Each time we find a maximal clique containing σ -1 (i) we cover (delete) all those edges in this clique. The number of cliques thus arise is exactly the intersection number of the graph. A bit thinking shows that the ST weighting algorithm can get the intersection number in O(|V (G)| 2 ) time.

Recall that, for any diamond-free elimination graph G, Lemma 4.5 says that the edge clique graph K e (G) is chordal. This enables us to use the algorithm of Gavril [START_REF] Gavril | Algorithm for minimum coloring, maximal clique, minimum covering by cliques and maximum independent set of a chordal graph[END_REF] to obtain the value of θ(K e (G)) = α(K e (G)), which is exactly i(G) by Theorem 3.1. Though the construction of K e (G) may be costly, this is another way to calculate the intersection number of a diamond-free elimination graph.

Family intersection number and Helly family intersection number

We use the convention that the maximal cliques of G have been indexed as

C(G) = {Q 1 , . . . , Q |C(G)| }.
We denote by C v (G) the subset of C(G) consisting of those maximal cliques which contain a vertex v and let

C Y (G) = {C ∈ C(G) : Y ⊆ V (C)} for any twin set Y. Let C(G) = C 1 (G) ∪ C 2 (G) ∪ C 3 (G) be a partition of the maximal cliques of G, where C 1 (G) = {Q i ∈ C(G) : Q has a special vertex}; C 2 (G) = {Q i ∈ C(G) : Q has a special edge but no special vertex}; C 3 (G) = {Q i ∈ C(G) :
Q has neither special edges nor special vertices}. We write R i and S i , respectively, for the sets of special vertices and special edges in Q i and let n i and m i be their respective cardinalities. Note that there are graphs G with C 3 (G) = C(G) and hence all n i and m i vanish; see the complete n-partite graph K 2,...,2 with n ≥ 3, which is also mentioned in Example 2.4.

Our aim in this section is to boil down some knowledge about C 1 (G), C 2 (G) and C 3 (G) to some estimates of i * (G) and i * h (G). We begin with a very easy and well-known result on set systems. Lemma 7.1 [3,Theorem 1.1.1] If A is a collection of distinct subsets of an n-set such that A i ∩ A j = ∅ for all A i , A j ∈ A, then |A| ≤ 2 n-1 . Further, if |A| < 2 n-1 , A can be extended to a collection of 2 n-1 subsets also satisfying the given intersection property.

We use lg for base 2 logarithm. For any complete graph K m , an implication of Lemma 7.1 is that

i * (K m ) = ⌈lg(m)⌉ + 1. (7)
For diamond-free graphs, Mahadev and Wang [START_REF] Mahadev | On uniquely intersectable graphs[END_REF] directly make the following generalization of Lemma 7.1.

(G) = {Q i }.
We deviate a bit to include a necessary condition for i(G) = i * (G) based on the structure of twin sets.

v ∈ V (G) \ V (Q), it holds that ({x} ∪ f (b)) ∩ f (v) = ∅.
A consequence of this fact is that for any set A and any v ∈ V (G) \ V (Q), whether or not f (v) ∩ A = ∅ is determined by the relationship between f (v) and A \ ({x} ∪ f (b)).

We construct a new mapping f ′ by

f ′ (v) =      f (b), for v ∈ Y, (f (v) ∪ f (b)) \ {x}, for v ∈ V (Q) \ Y, f (v), for v ∈ V (G) \ V (Q).
From our remark made above we see that

f ′ is a mutifamily representation of G satisfying f ′ (V (G)) ⊆ f (V (G)) \ {x}. This means that |f ′ (V (G))| ≤ i * (G) -1. So we have i(G) ≤ |f ′ (V (G))| < i * (G),
which is the desired contradiction. ✷

Let us switch back to our main line. We next prove that the quantity occurring in Theorem 7.2 is a general lower bound on the family intersection number.

Theorem 7.6 For every graph G, we have

i * (G) ≥ c s + ni≥1 ⌈lg(n i )⌉, ( 8
)
where c s is the number of maximal cliques with special vertices or special edges and n i is the number of special vertices in the ith maximal clique Q i .

Proof: Let f be a family representation of G of size i * (G). Clearly,

f (R i ) ∩ f (R j ) = ∅ for any two different cliques Q i , Q j ∈ C 1 (G). For any Q k ∈ C 2 (G)
, and any edge in S k , say ab, we assert that f ({a, b}) = ∅ must be disjoint from f (c) for any c / ∈ Q k . Otherwise, a, b, c will appear in some maximal clique of G, which must be different from

Q k for c / ∈ Q k , contradicting ab ∈ S k . We denote ab∈S k f ({a, b}) by O k . Our analysis above leads to the conclusion that f (R i ), O k are pairwise disjoint for Q i ∈ C 1 (G), Q k ∈ C 2 (G). It then follows that |f (V (G))| ≥ Q k ∈C2(G) |O k | + Qi∈C1(G) |f (R i )|. (9)
Restricting the representation f to the clique G(R i ) induced by R i , we deduce from Lemma 7.1, or more precisely, Eq. ( 7

), that |f (R i )| ≥ i * (G(R i )) = ⌈lg(n i )⌉ + 1. Also, we surely have |O k | ≥ 1 for each Q k ∈ C 2 (G). Thus, Eq. (9) gives i * (G) = |f (V (G))| ≥ |C 2 (G)| + ni≥1 (⌈lg(n i )⌉ + 1) = |C 1 (G)| + |C 2 (G)| + ni≥1 (⌈lg(n i )⌉) = c s + ni≥1 ⌈lg(n i )⌉, (10)
as required. ✷ Theorem 7.2 means that diamond-free graphs attain the lower bound given by Theorem 7.6. We cannot characterize all such graphs which have the family intersection number as c s + ni≥1 ⌈lg(n i )⌉. But for the Helly family representations, we can do a bit better.

Theorem 7.7 For every graph

G, i * h (G) ≥ |C(G)| + ni≥1 ⌈lg(n i )⌉, (11)
with equality if and only if

Qi∈C Y (G)∩C1(G) 2 ⌈lg(ni)⌉ ≥ |Y | (12)
for each twin set Y of G, where n i is the number of special vertices in the ith maximal clique

Q i and we set Qi∈C Y (G)∩C1(G) 2 ⌈lg(ni)⌉ as 1 when C Y (G) ∩ C 1 (G) = ∅.
Proof: Consider a Helly family representation f of G. For any Q i ∈ C(G), we deduce from the Helly property of

f that f (V (Q i )) = ∅. Moreover, since C(G) is the set of maximal cliques, the sets f (V (Q i )), i = 1, . . . , |C(G)|, are pairwise disjoint. Observe that for any Q i ∈ C 1 (G), we have f (R i ) ∩ ( j =i f (V (Q j ))) = ∅. In addition, Lemma 7.1 implies |f (R i )| ≥ ⌈lg(n i )⌉ + 1. Therefore, we have i * h (G) ≥ Qi∈C(G)\C1(G) |f (V (Q i ))| + Qi∈C1(G) |f (R i )| ≥ Qi∈C(G)\C1(G) 1 + ni≥1 (⌈lg(n i )⌉ + 1) = |C 2 (G)| + |C 3 (G)| + ni≥1 (⌈lg(n i )⌉ + 1), = |C(G)| + ni≥1 ⌈lg(n i )⌉, (13)
establishing Eq. [START_REF] Chandran | Fast generation of all perfect elimination orderings of a chordal graph[END_REF].

Assume now

i * h (G) = |C(G)| + ni≥1 ⌈lg(n i )⌉, (14)
which means that the equality holds throughout Eq. ( 13). This then gives

(i) |f (V (Q i ))| = 1 for Q i ∈ C(G) \ C 1 (G)
-This condition also follows from (ii) and (iii) below, therefore it will not be used in the sequel;

(ii) |f (R i )| = ⌈lg(n i )⌉ + 1 for Q i ∈ C 1 (G); (iii) f (V (G)) = ( Qi∈C(G)\C1(G) f (V (Q i ))) ∪ ( Qi∈C1(G) f (R i )).
Consider a twin set Y . For any v ∈ Y, since f satisfies the Helly property, we deduce from (iii) that

Γ ⊆ f (v) ⊆ Γ ∪ ( Qi∈C1(G)∩C Y (G) f (R i ) \ (f (R i ))), (15)
where Γ = (

Qi∈C Y (G)∩C1(G) f (R i )) ∪ ( Qi∈C Y (G)\C1(G) (f (V (Q i )))).
Note that the statement (ii) implies that f (R i ) cannot have more than one element, as a set of ⌈lg(n i )⌉ -1 elements cannot have n i > 2 ⌈lg(ni)⌉-1 different subsets. Thus, by virtue of the Helly property, we get

|f (R i ) \ f (R i )| = ⌈lg(n i )⌉.
This in turn tells us that for each i, f (R i ) \ f (R i ) has totally 2 ⌈lg(ni)⌉ distinct subsets. Finally, by Eq. ( 15) and the fact that f (R i ) ∩ f (R j ) = ∅ for any i = j, to ensure the representing sets of vertices in Y be pairwise distinct, we find then that Eq. ( 12) must hold.

To prove that Eq. ( 12) guarantees the validity of Eq. ( 14), we trace the argument above in the opposite direction. We construct a representation f whose underlying set is {1, 2, . . . , |C(G)|} ∪ ( Qi∈C1(G) {x i,1 , . . . , x i,⌈lg(ni)⌉ }) and its cardinality matches the lower bound of i * h (G). We assign the image of f twin set by twin set. For any twin set Y, suppose that

C Y (G) = {Q i1 , . . . , Q i k }. Since Qi∈C Y (G)∩C1(G) 2 ⌈lg(ni)⌉ ≥ |Y |, there is an injection from Y to 2 S Q i ∈C Y (G)∩C 1 (G) {xi,1,...,x i,⌈lg(n i )⌉ } , say g Y . For any v ∈ Y, we put f (v) = g Y (v) ∪ {i 1 , . . . , i k }. Clearly, for any u, w ∈ V (G), f (u) ∩ f (w) = ∅ if
and only if u and w are included in a common maximal clique, thereby showing that f is a representation of G. Moreover, we have

f (u) ∩ ( Qi∈C1(G) {x i,1 , . . . , x i,⌈lg(ni⌉) }) = f (w) ∩ ( Qi∈C1(G) {x i,1 , . . . , x i,⌈lg(ni)⌉ })

Purple graphs and intersection numbers

Owing to Theorem 7.7, we define a purple graph to be a graph G for which Eq. ( 14) holds. Observe that Eq. ( 8) coincides with Eq. ( 11 where c s is the number of maximal cliques with special vertices or special edges and n i is the number of special vertices in the ith maximal clique Q i ;

(iii) Eq. ( 12) is valid for each twin set Y ⊆ V (G).

In Example 5.6, we observe that all diamond-free graphs are maximal clique irreducible. Here comes an immediate corollary of Theorem 8.1.

Corollary 8.2 Each diamond-free graph is a purple graph.

Proof: Let G be a diamond-free graph. By Theorem 8.1 we only need to show that each twin set Y of G satisfies Eq. ( 12).

If Y is a singleton set, Eq. ( 12) is trivially true. For the remaining case, as G is diamond-free, the result of Mahadev and Wang reported in Example 4.7 implies that C Y (G) has only one element, say Q j . We deduce from Lemma 7.4 that R j = Y and hence Q j ∈ C 1 (G). This tells us that |Y | = n j ≤ 2 ⌈lg(nj )⌉ = Qi∈C) Y (G)∩C1(G) 2 ⌈lg(lg(ni)⌉ , finishing the proof. ✷

We remark that Theorem 7.2 can be easily seen from Theorem 8.1 and Corollary 8. (ii) G is twin-free;

(iii) The intersection number and the family intersection number of G are equal.

Proof: (i) ⇒ (ii): To prove that G is twin-free, it suffices to show that each twin set Y of G must have size 1. Since G is purple, Theorem 7.7 asserts that Eq. ( 12) holds in this case. For each clique In view of Corollary 8.2, the equivalence between statements (ii) and (iii) in Theorem 8.3 generalizes the equivalence of statements (ii) and (iii) in Theorem 1.4. Note that the implications of (ii) ⇒ (iii) and (iii) ⇒ (i) in Theorem 8.3 do not rely on the fact that G is purple. construct a mapping f 1 according to the rule

Q i ∈ C Y (G) ∩ C 1 (G),
f 1 (v) =      f (v), for v ∈ R i , f (v) ∪ f (R i ), for v ∈ V (Q i ) \ R i , f (v), for v ∈ V \ V (Q i ),
and another mapping f 2 by

f 2 (v) =      f (v), for v ∈ R i , (f (v) ∪ f (R i )) \ {x}, for v ∈ V (Q i ) \ R i , f (v), for v ∈ V \ V (Q i ).
Then we can check that f 1 and f 2 are both family representations of G sharing a common underlying set with f. However, the assumption V (Q i ) = R i implies that we can pick a vertex c ∈ V (Q i ) \ R i . We Proof: If G is uim and twin-free, then G is surely ui.

Conversely, taking into account that a graph must be uim provided it is both ui and twin-free, our task is to show that G is twin-free whenever it is purple and ui. Since G is ui, Theorem 9. Mahadev and Wang have proved that each diamond-free graph is uniquely representable with respect to multifamily representation [START_REF] Mahadev | On uniquely intersectable graphs[END_REF]Theorem 3.2]. By this result and Corollary 8.2, we can see that Theorem 9.3 is stronger than asserting the equivalence of statements (i) and (ii) in Theorem 1.4, while Corollary 9.4 is stronger than claiming the equivalence of statements (i) and (iii) in Theorem 1.4, respectively.

Theorem 1 . 4 (

 14 Mahadev and Wang) [START_REF] Mahadev | On uniquely intersectable graphs[END_REF] Theorem 3.8] If a graph G is diamond-free, then the following are equivalent:(i) G is uniquely representable with respect to family representation;

Fig. 1 :

 1 Fig. 1: The diamond.

Lemma 2 . 2

 22 The equality i h (G) = |C(G)| holds for any graph G. Proof: A Helly multifamily representation f of size |C(G)| can be obtained by letting S = C(G) and f

Fig. 2 :

 2 Fig.2: i h and i * are incomparable.

  To prove Theorem 3.1, we transform CPI and CPII to their dual maximization problems as below. Packing Problem I (PPI) Maximize: e∈E(G) w(e) Subject To: e∈E(C) w(e) ≤ 1 for each C ∈ C G With: w(e) ∈ {0, 1} for each e ∈ E(G). Packing Problem II (PPII) Maximize: e∈E(G) w(e) Subject To: e∈E(C) w(e) ≤ 1 for each C ∈ C G With: w(e) ≥ 0 for each e ∈ E(G).

Fig. 3 :

 3 Fig. 3: A diamond-free elimination graph.

Fig. 4 :

 4 Fig.4: A graph and its edge clique graph.

Fig. 5 :

 5 Fig. 5: The Tsuchiya graph T10 and the set F5.

Theorem 5 . 5 G

 55 2 and Lemma 5.3. ✷ Lemma 5.3 together with Theorem 5.4 goes through to deduce the following result. is maximal clique irreducible if and only

For a graph

  G, an ordering π of C(G) is a way to label exactly one clique from C(G) as C i for each i = 1, . . . , |C(G)|; we express this fact by writing π = (C 1 , . . . , C |C(G)|

Fig. 6 :

 6 Fig. 6: A member of SSH \ SH.

Example 5 . 16

 516 It is surely true that if the size of no C ∈ C(G) exceeds 2 then each clique in C(G) has a special edge. This observation together with Lemma 5.11 yields that the Petersen graph demonstrated in Fig.7is a member of HCH. But we can easily check that the maximal cliques of Petersen graph do not possess any circular ordering. This means that the Petersen graph does not belong to HCA. Consequently, we arrive at HCH \ HCA = ∅.

Fig. 7 :

 7 Fig. 7: The Pertersen graph.

Lemma 6 . 1

 61 Let σ be a vertex ordering of graph G. If w is the weight function arising from the ST weighting algorithm with σ as an input, we can produce an intersection representation of G of size C∈C G w(C). Proof: First we show that C∈C G w(C) is a feasible solution to the linear program CPII, i.e., for each e ∈ E(G), we have e∈E(C) C∈C G w(C) ≥ 1.

Theorem 7 . 5

 75 Let G be a graph. If i(G) = i * (G), then each twin set Y of G with |C Y (G)| = 1 is a singleton set. Proof: We shall assume the opposite, namely there exists a twin set Y with |C Y (G)| = 1 and |Y | ≥ 2, and derive a contradiction. Since |C Y (G)| = 1, there exists a unique Q ∈ C 1 (G) such that C Y (G) = {Q}. We take two distinct vertices a, b ∈ Y. Let f be a family representation of G satisfying f (V (G)) = i * (G). Since f (a) = f (b), w.l.o.g., we can assume that there exists x ∈ f (a) \ f (b). Clearly, for any

  when u and w are twins and f (u) ∩ {1, 2, . . . , |C(G)|} = f (w) ∩ {1, 2, . . . , |C(G)|} when u and w are not twins. Hence, f is a family representation of G. Finally, as a consequence of i ∈ f (V (Q i )), i = 1, . . . , |C(G)|, f must satisfy the Helly property. This completes the proof. ✷

  ) when C 3 (G) = ∅. It is noteworthy that C 3 (G) = ∅ if and only if G is maximal clique irreducible, in other words, G ∈ SSH. So by Theorems 7.6 and 7.7 we have the following result. Theorem 8.1 For any maximal clique irreducible graph G, the following statements are equivalent: (i) G is a purple graph; (ii) The family intersection number and the Helly family intersection number of G are both c s + ni≥1 ⌈lg(n i )⌉,

2 . 8 . 3

 283 Theorem For any purple graph G, the following statements are equivalent:(i) Each twin set Y with |C Y (G)| = 1 is a singleton set;

  if any, Lemma 7.4 implies that R i is a twin set of G and C Ri (G) = {Q i }. So we obtain from statement (i) that n i = |R i | = 1. By Eq. (12) it follows that |Y | ≤ Qi∈C Y (G)∩C1(G) 2 ⌈lg(ni)⌉ = 1.This is the result.(ii) ⇒ (iii): This is trivial. (iii) ⇒ (i): This is Theorem 7.5. ✷

  clearly have |f 2 (c)|=|f 1 (c)| -1 and hence we have |f (c)| = |f 1 (c)| or |f (c)| = |f 2 (c)|. If the former holds, then take f′ = f 1 ; otherwise let f ′ = f 2 . ✷Now we return to purple graphs.Theorem 9.3 A purple graph G is uniquely representable with respect to family representation if and only if it is both twin-free and uniquely representable with respect to multifamily representation.

  2 implies that each twin set Y of G with |C Y (G)| = 1 is a singleton set, namely statement (i) of Theorem 8.3 is established. Then we apply Theorem 8.3 to the purple graph G and conclude that G is twin-free, finishing the proof. ✷ In light of Theorem 8.3 and Theorem 9.3, we have an immediate corollary. Corollary 9.4 A purple graph G is uniquely representable with respect to family representation if and only if i * (G) = i(G) and G is uniquely representable with respect to multifamily representation.

  1 and Lemma 4.5, as desired.

✷

Let us look around for some examples of diamond-free elimination graphs.

Example 4.7 As a class of graphs including all bipartite graphs, diamond-free graphs have attracted much attention. Mahadev and Wang

[START_REF] Mahadev | On uniquely intersectable graphs[END_REF] Proposition 2.8]

show that a graph G is diamond-free if and only if every edge of G lies in a unique maximal clique. We thus know that the class of diamond-free graphs is a subclass of diamond-free elimination graphs. An application of Theorem 4.6, or the remark preceding Theorem 4.6, says that the intersection numbers of these graphs are easy to determine.

  1 and then we can check that u i w i ∈ E(C i ) is a special edge. By appealing to Theorem 5.5, the result follows. ✷ Evidently, all Tsuchiya graphs T 2t posed in Example 5.1 with t > 3 are contained in HCA. So by Corollary 5.7, we have the following result. Corollary 5.8 Each Tsuchiya graph T 2t with t > 3 satisfies

  Theorem 7.2 (Mahadev and Wang)[START_REF] Mahadev | On uniquely intersectable graphs[END_REF] Lemma 3.7.] Let G be a diamond-free graph. Then we have i * (G) = c s + ni≥1,Qi∈C(G) ⌈lg(n i )⌉, where c s is the number of maximal cliques possessing either special vertices or special edges and n i is the number of special vertices in the ith maximal clique Q i .Inspired by Theorem 7.2, we now have a look at the lower bounds of the family intersection number i * (G) and Helly family intersection number i * h (G). We have the following two simple observations, which indicate the connection between twin structure and clique structure.Lemma 7.3 xRy if and only ifC x (G) = C y (G). For any i = 1, . . . , |C(G)|, R i iseither empty or a twin set. Moreover, if R i is nonempty, we have C Ri

	Lemma 7.4

This work was supported by Science and Technology Commission of Shanghai Municipality (No. 08QA14036, 09XD1402500), Chinese Ministry of Education (No. 108056), National Natural Science Foundation of China (No. 10871128), and Ky and Yu-Fen Fan Fund of American Mathematical Society. We thank the anonymous referees for many useful comments.

Unique representability

In this last section we will present some results on the unique representability problem, especially for purple graphs.

By checking the proof of the part of Eq. ( 12) ⇒ Eq. ( 14) in establishing Theorem 7.7, we can see that all possible minimum-size Helly family representations for a purple graph G have been enumerated there. Actually, the set of such representations is in one-to-one correspondence with the set Y {g Y } where Y runs over all twin sets of G and g Y runs over all injections from Y to 2

Especially, if G is twin-free, each twin set Y consists of only one element and the corresponding T Y also only consists of one element, namely the empty set. Thus we know that any twin-free purple graph G is uniquely representable with respect to Helly family representation. Clearly, any twin-free graph is uniquely representable with respect to family representation if and only if it is uniquely representable with to multifamily representation. It implies that G is also uniquely representable with respect to Helly multifamily representation. We point out below that a more general result holds true and has a simpler proof.

For any two minimum-size Helly multifamily representations f 1 and f 2 of G, let π be the bijection from

The following result is an extension of Theorem 1.3. It means that the statement (i) in Theorem 8.3 has a lot to do with the unique representability of graphs. Our proof is similar to that used by Mahadev and Wang [START_REF] Mahadev | On uniquely intersectable graphs[END_REF] in proving Theorem 1.4.


Ruy Fabila-Monroy

David Flores-Peñaloza

Clemens Huemer
email: clemens@ma4.upc.edu

Ferran Hurtado
email: ferran.hurtado@upc.edu

Jorge Urrutia
email: urrutia@math.unam.mx

David R Wood
email: woodd@unimelb.edu.au

On the Chromatic Number of some Flip Graphs

Keywords: chromatic number, flip graph, geometric graph, Hamiltonian path, perfect matching, triangulation Mathematics Subject Classification: 05C15 (Coloring of graphs and hypergraphs)

This paper studies the chromatic number of the following four flip graphs (under suitable definitions of a flip):

• the flip graph of perfect matchings of a complete graph of even order,

• the flip graph of triangulations of a convex polygon (the associahedron),

• the flip graph of non-crossing Hamiltonian paths of a set of points in convex position, and

• the flip graph of triangles in a convex point set.

We give tight bounds for the latter two cases and upper bounds for the first two.

Introduction

Given a class C of combinatorial objects of a given kind and a transformation (flip) between these objects, a flip graph is defined as the graph whose vertex set is C, where two vertices are adjacent whenever the corresponding objects differ by a flip. Flip graphs have received considerable attention in the past. Properties such as Hamiltonicity, connectivity and diameter have been widely studied [START_REF] Cummins | Hamilton circuits in tree graphs[END_REF][START_REF] Goddard | Distances between graphs under edge operations[END_REF][START_REF] Lucas | The rotation graph of binary trees is Hamiltonian[END_REF][START_REF] Sleator | Rotation distance, triangulations, and hyperbolic geometry[END_REF]. This interest is very likely a consequence of the practical applications of these properties. For example, Hamiltonicity allows for rapid generation of the given combinatorial objects. We refer the interested reader to the survey [START_REF] Bose | Flips in planar graphs[END_REF].

A k-coloring of a graph G is a function that assigns one of k colors to each vertex of G, such that adjacent vertices receive distinct colors. The chromatic number χ(G) is the least integer k for which there is a k-coloring of G. The chromatic number can be formulated in terms of homomorphisms. A homomorphism from a graph G to a graph H is a mapping from V (G) to V (H) such that the images of any two adjacent vertices in G are adjacent in H. In this sense χ(G) is the minimum positive integer m such that there exists a homomorphism from G to the complete graph K m . The composition of homomorphisms is again a homomorphism. Therefore if there exists a homomorphism from G to H then χ(G) ≤ χ(H).

The chromatic number of flip graphs has received little attention, with only a few papers concentrating on this parameter (see for example [START_REF] Estivill-Castro | On the chromatic number of tree graphs[END_REF]). This paper studies the chromatic number of some flip graphs. We first consider three flip graphs defined on sets of points in convex position. (A set of points in the plane is in convex position if it forms the vertex-set of a convex polygon.) We then consider the flip graph on the perfect matchings of a complete graph of even order.

A geometric non-crossing graph is a planar graph in which the vertices are embedded as points in the plane, and where the edges are embedded as non-crossing straight line segments. Throughout the paper, S n will denote a set of n points in convex position in the plane, and the term convex hull will refer to the boundary of the convex polygon having those points as vertex set. All of the considered graphs, except the flip graph of perfect matchings, have all of their vertices associated to non-crossing geometric graphs having S n as vertex set. We remark that any underlying convex point set of the same size induces the same graphs.

This paper is organized as follows. In Section 2 we determine the exact chromatic number for noncrossing geometric Hamiltonian paths having S n as their set of vertices. In Section 3 we define a certain flip graph on the triangles with vertices in S n and determine its chromatic number up to a constant multiplicative factor. In Section 4 we give an upper bound on the chromatic number for the flip graph of the triangulations of S n . In Section 5 we consider a flip graph on the perfect matchings of K 2n and give an upper bound on its chromatic number. (It should be stressed that in this graph no geometry is considered.) In Section 6 we conclude with some open problems and remarks.

Geometric Non-Crossing Hamiltonian Paths

Let G n be the graph whose vertex set is the set of all geometric non-crossing paths with vertex set S n . Two paths Γ and Γ ′ in V (G n ) are adjacent if and only if Γ ′ is obtained from Γ by deleting some edge e and adding some edge f . (See Figure 1.) We say that Γ ′ is obtained from Γ by flipping the edge e. We point out that e and f may cross or they may share an endpoint. Rivera-Campo [START_REF] Rivera-Campo | Hamilton cycles in the path graph of a set of points in convex position[END_REF] and Urrutia-Galicia [START_REF] Urrutia-Galicia | Algunas propiedades de gráficas geométricas[END_REF] proved that G n is Hamiltonian. We determine χ(G n ). Proof: Since G 3 ≃ K 3 , assume n ≥ 4. For all integers i ∈ [0, n -3], let D i be the set of paths in V (G n ) that contain exactly i edges not in the convex hull of S n . (See Figure 1). Note that the set D 0 consists of n paths, all of whose edges are in the convex hull of S n . Each element of D 0 is obtained by removing one edge of the convex hull of S n . Clearly any two elements of

D 0 are adjacent in G n , therefore D 0 induces a complete subgraph of G n . This proves that χ(G n ) ≥ n. Let H i be the subgraph induced in G n by D 0 ∪ • • • ∪ D i . We prove χ(G n ) ≤ n by showing how to extend an n-coloring of H i-1 to an n-coloring of H i for every i ∈ [1, n -3]. For this, let Γ i be a path in D i .
For extending an n-coloring of H 0 to one of H 1 we use the next two properties of G n . (1) The set D 1 induces a perfect matching in G n . (2) Every adjacent pair in D 1 together with its neighborhood in H 1 induces a K 4 in G n . Both properties follow because, on one hand, flipping an edge of Γ 1 that is in the convex hull of S n yields a path in D 2 . On the other hand, flipping the edge of Γ 1 that is not in the convex hull of S n yields either one path in D 1 , or one of two different paths in D 0 . Since n ≥ 4, each pair of adjacent paths in D 1 can be colored with colors different to those of its neighbors in D 0 .

For extending an n-coloring of H i-1 to one of H i when i ≥ 2, we use the next two properties of G n . (1) The set D i is an independent set in G n . [START_REF] Bose | Partitions of complete geometric graphs into plane trees[END_REF] The vertex of G n corresponding to the path Γ i has degree 2 in H i . The first property follows because, on one hand, flipping an edge of Γ i that is in the convex hull of S n yields a path in D i+1 . On the other hand, flipping an edge of Γ that is not in the convex hull of S n yields a path in D i-1 . The latter property follows because the only edges of Γ that are not in the convex hull of S n that can be flipped, are the first and last when walking from one leaf of Γ to the other.

Since n colors are needed to color D 0 , and any n-coloring of D 0 can be extended to an n-coloring of G n , the result follows. ✷

Triangle Graph

We introduce a new flip graph G △ (n), whose vertex set is the set of triangles with endpoints in S n , two of which are adjacent if they share an edge and their interiors are disjoint. (See Figure 2.) We prove that this graph has chromatic number Θ(log n).

Fig. 2: The graph G △ [START_REF] Hurtado | Graph of triangulations of a convex polygon and tree of triangulations[END_REF].

For the rest of this section, assume that the elements of S n are labeled {0, . . . , n -1} in clockwise order, and let any triangle be denoted by the set of its vertices.

Lemma 3.1 For every integer n ≥ 3, χ(G △ (n)) ≥ log 2 (n -1).
Proof: Let H be the subgraph of G △ (n) induced by all triangles containing 0 as a vertex. Suppose that H has a k-coloring. Let A i (with 1 ≤ i ≤ n -2), be the set of colors assigned to the triangles {0, i, j} (with i < j ≤ n-1); see Figure 3 (a). Observe that A r = A s for r = s. This follows from the fact that if r < s, the triangle {0, r, s} is adjacent to every triangle {0, s, k} (with s < k ≤ n -1); see Figure 3 (b). Thus, the color assigned to {0, r, s} is in A r but not in A s . The number of possible non-empty color subsets must be at least n -2. Therefore 2 k ≥ n -1, implying k ≥ log 2 (n -1) and χ(G △ (n)) ≥ log 2 (n -1). ✷

Note that the subgraph H of G △ considered in the proof of Lemma 3.1 is isomorphic to the so-called shift graph [START_REF] Hell | Graphs and homomorphisms[END_REF] of the set {1, 2, . . . , n -1}. It is folklore that its chromatic number is ⌈log 2 (n -1)⌉. Proof: Color the vertices of S 2m red and blue such that consecutive vertices along the convex hull have distinct colors. Note that the subgraph H of G induced by the blue points is isomorphic to G △ (m). Map every triangle t in V (G) to a triangle t ′ in V (H) as follows: If i is a red vertex of t, substitute it by the blue vertex i + 1, where addition is modulo 2m. Observe that triangles whose vertices are all blue are mapped onto themselves. Since adjacent triangles in G are mapped to adjacent triangles in H, this mapping induces a homomorphism from G to H (see Figure 3). The result follows. ✷

Lemma 3.3 For every integer m ≥ 3, χ(G △ (2m)) ≤ χ(G △ (m)) + 3.
Proof: We use a similar technique to that used in Theorem 2.1. Let G ′ be the subgraph of G △ (2m) induced by all those triangles of S 2m that have at least one edge in the convex hull of S 2m . Let τ = {i, i + 1, j} be any such triangle. S 2m -{i, i + 1, j} can be partitioned into two maximal subsets of consecutive points along the convex hull, namely the points from i + 1 to j and the points from j to i, which we denote by l τ and r τ respectively. Let the order of τ be min{|l τ |, |r τ |}. For i ∈ [0, m -2], let D i be the subset of V (G ′ ) of all triangles of order i. Note that the subgraph of G ′ induced by D m-2 has maximum degree 2 and therefore chromatic number at most 3. Note that every vertex of D i is only adjacent to at most two vertices in

D i ∪ • • • ∪ D m-2 . Thus any 3-coloring of D i+1 ∪ • • • ∪ D m-2 can be extended to a 3-coloring of D i ∪ D i+1 ∪ • • • ∪ D m-2 . Therefore χ(G ′ ) = 3.
Let G be the subgraph of G △ (2m) induced by all the triangles without edges of the convex hull of S 2m . Observe that V (G) ∪ V (G ′ ) = V (G △ (2m)). Since there is a 3-coloring of G ′ and (by Lemma 3.2) there is a coloring of G with χ(G △ (m)) colors, there is a coloring of G △ (2m) with χ(G △ (m)) + 3 colors. ✷

We now have:

Theorem 3.4 For every integer n ≥ 3, log 2 (n -1) ≤ χ(G △ (n)) ≤ 3⌈log 2 (n)⌉ -4. Proof: Let F (k) = χ(G △ (2 k )). By Lemma 3.3, F (k) ≤ F (k -1) + 3. Observe that χ(G △ (4)) = 2. Thus F (k) ≤ 3k -4 and therefore χ(G △ (2 k )) ≤ 3k -4.
For n = 2 k , let m be the smallest power of 2 greater than n.

Since G △ (n) is a subgraph of G △ (m), we can color the vertices of G △ (n) with χ(G △ (m)) ≤ 3 log 2 (m) -4 = 3⌈log 2 (n)⌉ -4 colors. ✷ 4

Triangulations of a Convex Polygon

We consider a flip graph on the triangulations of S n . Let G T (n) be the graph whose vertex set is the set of triangulations of S n , where two triangulations T 1 and T 2 are adjacent in G T (n) whenever they differ by one edge flip; that is, there exist edges e ∈ T 1 and f ∈ T 2 such that T 2 is obtained from T 1 by deleting e and adding f (see Figure 5). Much is known about G T (n). This is probably because there is a bijection between triangulations of the n-gon and binary trees with n -2 interior nodes. A flip in a triangulation corresponds to a rotation in its corresponding binary tree. Lucas [START_REF] Lucas | The rotation graph of binary trees is Hamiltonian[END_REF] proved that G T (n) is Hamiltonian. Sleator et al. [START_REF] Sleator | Rotation distance, triangulations, and hyperbolic geometry[END_REF] proved that the diameter of G T (n) is 2n -10. Lee [START_REF] Lee | The associahedron and the triangulations of the n-gon[END_REF] proved that the automorphism group of G T (n) is the dihedral group of symmetries of a regular n-gon. Lee also proved that G T (n) can be realized as the skeleton of an (n -3)-dimensional convex polytope called the associahedron. Most of these results are proved again in [START_REF] Hurtado | Graph of triangulations of a convex polygon and tree of triangulations[END_REF] using a unifying framework called the tree of triangulations. We give an upper bound on the chromatic number of G T (n).

Theorem 4.1 For every integer n ≥ 3, χ(G T (n)) ≤ ⌈ n 2 ⌉.
Proof: It is well known that for n even, the set of n 2 edges between the vertices of S n can be partitioned into n 2 edge-disjoint geometric non-crossing paths (see [START_REF] Lucas | Recreations Mathématiques[END_REF][START_REF] Bose | Partitions of complete geometric graphs into plane trees[END_REF] and Figure 6 for an example with n = 6). where f (1) = 1. Hence (ii)

f (n) = (2n -1)!! = (2n -1)(2n -3)(2n -5) . . . 1 = (2n)! 2 n n! .
By Stirling's Approximation,

f (n) = (2n)! 2 n n! ≈ √ 2 2n e n .
Also observe that M(K 2n ) is n(n -1)-regular. Furthermore, the open neighborhood of each vertex of M(K 2n ) induces a perfect matching; thus M(K 2n ) has no K 4 subgraph.

We now give an upper bound on χ(M(K 2n )). To do so, we use the fact that χ(M(K n,n )) = 2. In [START_REF] Hernando | Graphs of non-crossing perfect matchings[END_REF], the flip graph of the non-crossing geometric matchings of a set of 2n points in convex position is shown to be bipartite. This graph is actually a subgraph of M(K n,n ). Using the same arguments as in [START_REF] Hernando | Graphs of non-crossing perfect matchings[END_REF] we show that M(K n,n ) is bipartite: Let {1, . . . , n} and {1 ′ , . . . , n ′ } be the color classes of K n,n . Then each perfect matching of M(K n,n ) can be interpreted as a permutation σ of {1, . . . , n}, where (ii) Note that the operator !! is called double factorial in the literature. σ(i) = j ′ if i is matched to j ′ . Now, two perfect matchings of M(K n,n ) are adjacent if and only if their associated permutations differ by a transposition. Thus, these associated permutations have different parity and consequently M(K n,n ) is bipartite. Thus we obtain a coloring of M(K 2n ) using 2(2n -2) = 4n -4 colors. ✷

Open Problems

The most challenging open problems arising from this work are to determine the chromatic numbers of G T (n) and M(K 2n ). Despite our efforts, we have not been able to obtain non-trivial lower bounds for these graphs. We can formulate the following educated guess on the chromatic number of M(K 2n ).

Conjecture 6.1 For every integer n ≥ 2, χ(M(K 2n )) = n + 1.

We have verified this conjecture with the aid of a computer for n = 2, 3, 4.

We have studied M(K 2n ), but it would be very interesting to study M(G) for other graphs.

There is another flip graph, M ′ (G), related to M(G). M ′ (G) has as its vertex set the perfect matchings of G, where two matchings are now adjacent if and only if their symmetric difference is a cycle of arbitrary length. We have yet to study its chromatic number.

With respect to χ(G T (n)), the problem seems far more intriguing since we not only do not have a non-trivial lower bound, but we also believe that our upper bound is far from being tight: Let us mention that we do not have any strong evidence on the conjectured upper bound, and the tight value might be Θ(log log(n)) or Θ(polylog(n)), say, but we have chosen a precise value as more stimulating for research.

It would be interesting to see which techniques will be capable of improving the lower bounds of both of these graphs. It is likely that such techniques will turn out to be useful in determining the chromatic number of other graphs as well.

Theorem 2 . 1 0 D 1 D 2 Fig. 1 :

 210121 Fig. 1: G5 drawn with vertices grouped by the number of non-convex hull edges.

Lemma 3 . 2

 32 For every integer m ≥ 3, let G be the subgraph of G △ (2m) induced by all the triangles without edges in the convex hull of S 2m . Then χ(G) = χ(G △ (m)).

Fig. 3 :

 3 Fig. 3: Illustration of Lemma 3.1 (with s = 6). (a) The triangles considered in As are those having the segment 0s as its right side. (b) The triangle {0, r, s} (with r < s) is adjacent in H to all the triangles considered in As.

1 Fig. 4 :

 14 Fig. 4: The homomorphism between G and G △ (m).

Fig. 5 :

 5 Fig. 5: The graphs GT (5) and GT (6).

Fig. 7 :

 7 Fig. 7: The graph M(K6).

Theorem 5 . 1

 51 For every integer n ≥ 2, χ(M(K 2n )) ≤ 4n -4.Proof: Let {1, . . . , n} and {1 ′ , . . . , n ′ } be the color classes of K n,n , and let {1, . . . , 2n} be the set of vertices of K 2n . For every perfect matching M of K 2n , let U (M ) := {i ∈ V (K 2n )|(i, j) ∈ M and i > j} and D(M) := {i ∈ V (K 2n )|(i,j) ∈ M and i < j}. Assign to every matching M the number c(M ) := i∈D(M ) i mod (2n -2). Given two sets U and D, let M(U, D) be the set of matchings M such that U (M ) = U and D(M ) = D. The subgraph H U,D of M(K 2n ) induced by M(U, D) is a subgraph of M(K n,n ), and is thus 2-colorable. Color the vertices of H U,D with colors c(M ) and c ′ (M ) := c(M ) + 2n -2. We show now that if two matchings M and M ′ differ by a flip, then they receive different colors. Two cases arise: Either U (M ) = U (M ′ ) and D(M ) = D(M ′ ), or for some i = j, U (M ) = U (M ′ ) -{i} + {j} and D(M ) = D(M ′ ) -{j} + {i}. In the first case, M and M ′ belong to H U (M ),D(M ) and thus receive different colors. In the second case, c(M ) = c(M ′ )j + i. Since 1 ∈ D(M ) ∩ D(M ′ ) and 2n ∈ U (M ) ∩ U (M ′ ), then |i -j| ≤ 2n -3. Therefore c(M ) = c(M ′ ), and consequently the colors assigned to M and M ′ are different.

Conjecture 6 . 2

 62 lim n→∞ χ(G T (n)) = ∞ and χ(G T (n)) = O(log(n)).

† Research of C. Huemer and F. Hurtado supported by projects MEC MTM2006-01267 and Gen. Cat. 2005SGR00692. ‡ supported by CONACYT of Mexico, Proyecto SEP-2004-Co1-45876, and PAPIIT (UNAM), Proyecto IN110802. § Supported by a QEII Research Fellowship. Research initiated at the Universitat Politècnica de Catalunya, where supported by a Marie Curie Fellowship under contract MEIF-CT-2006-023865, and by projects MEC MTM2006-01267 and DURSI 2005SGR00692. 1365-8050

Label these paths P 1 , . . . , P n 2 . (Since G T (n) is a subgraph of G T (n + 1), assume n is even for the time being.) If an edge e belongs to P i , assign to it the weight w(e) = i. To every triangulation T of S n , assign the number e∈T w(e) mod n 2 . Let T 1 and T 2 be two adjacent triangulations of G T (n). That is, T 2 = T 1e + f for some crossing edges e and f . Since e and f cross, w(e) = w(f ), and thus the numbers associated to T 1 and T 2 are different. This induces a coloring of G T (n) with n 2 colors for n even and ⌈ n 2 ⌉ in general. ✷ The upper bound on χ(G T (n)) in Theorem 4.1 is non-trivial since, for example, Brooks' Theorem [START_REF] Brooks | On coloring the nodes of a network[END_REF] gives an upper bound of only n -3. However, χ(G T (n)) is in fact sublinear, as we now show. Johansson proved that for sufficiently large ∆, every triangle-free graph with maximum degree ∆ is O ∆ log ∆colorable; see [START_REF] Molloy | Graph colouring and the probabilistic method[END_REF]. The next theorem follows since G T (n) is (n -3)-regular and triangle-free.

We remark that the proof of Theorem 4.1 is constructive, whereas Johansson's proof is probabilistic.

Perfect Matchings of K 2n

Given any graph G, let M(G) be the graph whose vertex set is the set of perfect matchings of G, where two vertices of M(G) are adjacent whenever the symmetric difference of the corresponding perfect matchings is a cycle of length 4. (See Figure 7).

We remark that (contrary to the other graphs we study in this paper) we do not consider geometry in the definition of M(G). This is because the geometric version of this graph (i) is bipartite, as was shown by Hernando et al. [START_REF] Hernando | Graphs of non-crossing perfect matchings[END_REF]. Interestingly, the chromatic number turns out to be quite challenging when geometry is discarded.

We first determine the number of vertices of M(K 2n ). Let f (n) := |V (M(K 2n ))| be the number of perfect matchings of K 2n . Say V (K 2n ) = {v 1 , . . . , v 2n }. In every such matching, v 1 is matched with some vertex in {v 2 , . . . , v 2n }, and the remaining matching is isomorphic to a perfect matching of K 2n-2 . Every matching obtained in this way is distinct. Thus i) In the geometric version of this graph, the vertices are the non-crossing perfect matchings of a set of 2n points in convex position; two of which are adjacent whenever their symmetric difference is a cycle of length four.