Matroid Representation of Clique Complexes
Kenji Kashiwabara1, Yoshio Okamoto2? , and Takeaki Uno3
1

Department of Systems Science, Graduate School of Arts and Sciences, The
University of Tokyo, 3–8–1, Komaba, Meguro, Tokyo, 153–8902, Japan.
kashiwa@graco.c.u-tokyo.ac.jp
2
Institute of Theoretical Computer Science, Department of Computer Science, ETH
Zurich, ETH Zentrum, CH-8092, Zurich, Switzerland. okamotoy@inf.ethz.ch3National Institute of Informatics, 2–1–2, Hitotsubashi, Chiyoda, Tokyo, 101-8430,
Japan. uno@nii.jp

Abstract. In this paper, we approach the quality of a greedy algorithm
for the maximum weighted clique problem from the viewpoint of matroid
theory. More precisely, we consider the clique complex of a graph (thecollection of all cliques of the graph) and investigate the minimum number k such that the clique complex of a given graph can be represented as
the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted
clique problem” since a greedy algorithm is a k-approximation algorithm
for this problem. We characterize graphs whose clique complexes can be
represented as the intersection of k matroids for any k > 0. Moreover, we
determine the minimum number of matroids which we need to represent
all graphs with n vertices. This number turns out to be exactly n − 1.
Other related investigations are also given.

1

Introduction

A lot of combinatorial optimization problems can be seen as optimization problems on the corresponding independence systems. For example, for the minimum
cost spanning tree problem the corresponding independence system is the collection of all forests of a given graph; for the maximum weighted matching problem
the corresponding independence system is the collection of all matchings of agiven graph; for the maximum weighted clique problem the corresponding independence system is the collection of all cliques of a given graph, which is called
the clique complex of the graph. More examples are provided by Korte–Vygen [9].
It is known that any independence system can be represented as the intersection of some matroids. Jenkyns [7] and Korte–Hausmann [8] showed that agreedy algorithm is a k-approximation algorithm for the maximum weighted baseproblem of an independence system which can be represented as the intersectionof k matroids. (Their result can be seen as a generalization of the validity of the?

Supported by the Joint Berlin/Zürich Graduate Program “Combinatorics, Geometry, and Computation” (CGC), financed by ETH Zurich and the German Science
Foundation (DFG).

2

Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno

greedy algorithm for matroids, shown by Rado [13] and Edmonds [3].) So theminimum number of matroids which we need to represent an independence system as their intersection is one of the measures of “how complex an independence
system is with respect to the corresponding optimization problem.”In this paper, we investigate how many matroids we need to represent theclique complex of a graph as their intersection, while Fekete-Firla-Spille [5] investigated the same problem for matching complexes. We will show that theclique complex of a given graph G is the intersection of k matroids if and only
if there exists a family of k stable-set partitions of G such that every edge of
G is contained in a stable set of some stable-set partition in the family. This
theorem implies that the problem to determine the clique complex of a given
graph have a representation by k matroids or not belongs to NP (for any fixedk). This is not a trivial fact since in general the size of an independence system
will be exponential when we treat it computationally.
The organization of this paper is as follows. In Sect. 2, we will introduce
some terminology on independence systems. The proof of the main theorem will
be given in Sect. 3. In Sect. 4, we will consider an extremal problem related
to our theorem. In Sect. 5, we will investigate the case of two matroids morethoroughly. This case is significantly important since the maximum weighted
base problem can be solved exactly in polynomial time for the intersection of
two matroids [6]. (Namely, in this case, the maximum weighted clique problem
can be solved in polynomial time for any non-negative weight vector by Frank’salgorithm [6].) From the observation in that section, we can find the algorithm byProtti–Szwarcfiter [12] checks that a given clique complex has a representationby two matroids or not in polynomial time. We will conclude with Sect. 6.

2

Preliminaries

We will assume the basic concepts in graph theory. If you find something unfamiliar, see a textbook of graph theory (Diestel’s book [2] or so). Here we will fix
our notations. In this paper, all graphs are finite and simple unless stated otherwise. For a graph G = (V, E) we denote the subgraph induced by V 0 ⊆ V by
G[V 0 ]. The complement of G is denoted by G. The vertex set and the edge set ofa graph G = (V, E) are denoted by V (G) and E(G), respectively. A completegraph and a cycle with n vertices are denoted by Kn and Cn , respectively. The
maximum degree, the chromatic number and the edge-chromatic number (or thechromatic index) of a graph G are denoted by ∆(G), χ(G) and χ0 (G), respectively. A clique of a graph G = (V, E) is a subset C ⊆ V such that the induced
subgraph G[C] is complete. A stable set of a graph G = (V, E) is a subset S ⊆ Vsuch that the induced subgraph G[S] has no edge.
Now we introduce some notions of independence systems and matroids. For
details of them, see Oxley’s book [11]. Given a non-empty finite set V , an independence system on V is a non-empty family I of subsets of V satisfying: X ∈ I
implies Y ∈ I for all Y ⊆ X ⊆ V . The set V is called the ground set of thisindependence system. In the literature, an independence system is also called anMatroid representation of clique complexes

3

abstract simplicial complex . A matroid is an independence system I additionally satisfying the following augmentation axiom: for X, Y ∈ I with |X| > |Y |there exists z ∈ X \ Y such that Y ∪ {z} ∈ I. For an independence system I, a set X ∈ I is called independent and a set X 6∈ I is called dependent. A base and a circuit of an independence system is a maximal independent set and a minimal dependent set, respectively. We denote the family ofbases of an independence system I and the family of circuits of I by B(I)and C(I), respectively. Note that we can reconstruct an independence systemI from B(I) or C(I) as I = {X ⊆ V : X ⊆ B for some B ∈ B(I)} andI = {X ⊆ V : C 6⊆ X for all C ∈ C(I)}. In particular, B(I1 ) = B(I2 ) if andonly if I1 = I2 ; similarly C(I1 ) = C(I2 ) if and only if I1 = I2 . We can see thatthe bases of a matroid have the same size from the augmentation axiom, but it
is not the case for a general independence system.
Let I be a matroid on V . An element x ∈ V is called a loop if {x} is a circuitof I. We say that x, y ∈ V are parallel if {x, y} is a circuit of the matroid I. The
next is well known.
Lemma 2.1 (see [11]). For a matroid without a loop, the relation that “x isparallel to y” is an equivalence relation.
Let I1 , I2 be independence systems on the same ground set V . The intersection of I1 and I2 is just I1 ∩ I2 . The intersection of more independence systems
is defined in a similar way. Note that the intersection of independence systems is
also an independence system. Also note that the family of circuits of I1 ∩I2 is thefamily of the minimal sets of C(I1 ) ∪ C(I2 ), i.e., C(I1 ∩ I2 ) = min(C(I1 ) ∪ C(I2 )).
The following well-known observation is crucial in this paper.
Lemma 2.2 (see [4, 5, 9]). Every independence system can be represented as
the intersection of finitely many matroids on the same ground set.
Proof. Denote the circuits of an independence system I by C (1) , . . . , C (m) ,(i)and consider the matroid Ii with a unique circuit C(ITim) = {C } for eachi ∈ {1, . . . , m}. Then, the family of theTcircuits of i=1 Ii is nothing butm{C (1) , . . . , C (m) }. Therefore, we have I = i=1 Ii .
tu
Due to Lemma 2.2, we are interested in representation of an independence
system as the intersection of matroids. From the construction in the proof of
Lemma 2.2, we can see that the number of matroids which we need to represent
an independence system I by the intersection is at most |C(I)|. However, wemight do better. In this paper, we investigate such a number for a clique complex.

3

Clique Complexes and the Main Theorem

A graph gives rise to various independence systems. Among them, we will investigate clique complexes.
The clique complex of a graph G = (V, E) is the collection of all cliques of G.
We denote the clique complex of G by C(G). Note that the empty set is a clique

4

Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Unoand {v} is also a clique for each v ∈ V . So we can see that the clique complex isactually an independence system on V . We also say that an independence system
is a clique complex if it is isomorphic to the clique complex of some graph. Noticethat a clique complex is also called a flag complex in the literature.
Here we give some subclasses of the clique complexes. (We omit necessary
definitions.) (1) The family of the stable sets of a graph G is nothing but theclique complex of G. (2) The family of the matchings of a graph G is the cliquecomplex of the complement of the line graph of G, which is called the matchingcomplex of G. (3) The family of the chains of a poset P is the clique complex of
the comparability graph of P , which is called the order complex of P . (4) The
family of the antichains of a poset P is the clique complex of the complement of
the comparability graph of P .
The next lemma may be a folklore.
Lemma 3.1. Let I be an independence system on a finite set V . Then, I is aclique complex if and only if the size of every circuit of I is two. In particular,
the circuits of the clique complex of G are the edges of G.
Proof. Let I be the clique complex of G = (V, E). Since a single vertex v ∈ V
forms a clique, the size of each circuit is greater than one. Each dependent set ofsize two is an edge of the complement. Observe that they are minimal dependent
sets since the size of each dependent set is greater than one. Suppose that there
exists a circuit C of size more than two. Then each two elements in C form anedge of G. Hence C is a clique. This is a contradiction.
Conversely, assume that the size of every circuitof I is two. Then construct
a graph G0 = (V, E 0 ) with E 0 = {{u, v} ∈ V2 : {u, v} 6∈ C(I)}. Consider theclique complex C(G0 ). By the opposite direction which we have just shown, we
can see that C(C(G0 )) = C(I). Therefore I is the clique complex of G0 .
tu

Now we start studying the number of matroids which we need for the representation of a clique complex as their intersection. First we characterize thecase in which we need only one matroid. (namely the case in which a cliquecomplex is a matroid). To do this, we define a partition matroid. A partition
matroid is a matroid I(P) associated with a partition P = {P1 , P2 , . . . , Pr } of
V defined as I(P) = {I ⊆ V : |I ∩ Pi | ≤ 1 for all i ∈ {1, . . . , r}}. Observethat I(P) is a clique complex. Indeed if we construct a graph GP = (V, E)
from P as u, v ∈ V are adjacent in GP if and only if u, v are elements of distinct partition classes in P, then we can see that I(P) = C(GP ). Note that
C(I(P)) = {{u, v} ∈ V2 : {u, v} ⊆ Pi for some i ∈ {1, . . . , r}}. Also note that
GP is a complete r-partite graph with the partition P. In the next lemma, theequivalence of (1) and (3) is also noticed by Okamoto [10].
Lemma 3.2. Let G be a graph. Then the following are equivalent. (1) The cliquecomplex of G is a matroid. (2) The clique complex of G is a partition matroid.
(3) G is complete r-partite for some r.
Proof. “(2) ⇒ (1)” is clear, and “(3) ⇒ (2)” is immediate from the discussion
above. So we only have to show “(1) ⇒ (3).” Assume that the clique complex C(G) is a matroid. By Lemma 3.1, every circuit of C(G) is of size two,Matroid representation of clique complexes

5

which corresponds to an edge of G. So the elements of each circuit are parallel.
Lemma 2.1 says that the parallel elements induce an equivalence relation on
V (G), which yields a partition P = {P1 , . . . , Pr } of V (G). Thus, we can see that
G is a complete r-partite graph with the vertex partition P.
tu
For the case of more matroids, we use a stable-set partition. A stable-set
partition of a graph G = (V, E) is a partition P = {P1 , . . . , Pr } of V such thateach Pi is a stable set of G. The following theorem is the main result of this paper.
It tells us how many matroids we need to represent a given clique complex.
Theorem 3.3. Let G = (V, E) be a graph. Then, the clique complex C(G) canbe represented as the intersection of k matroids if and only if there exist k stableset partitions P (1) , . . . , P (k) such that {u, v} ∈ V2 is an edge of G if and onlySkTk
if {u, v} ⊆ S for some S ∈ i=1 P (i) (in particular, C(G) = i=1 I(P (i) )).
To show the theorem, we use the following lemmas.

Lemma 3.4. Let G = (V, E) be a graph. If the clique complex C(G) can be represented as the intersection of k matroids,
then there exist k stable-set partitions
TP (1) , . . . , P (k) such that C(G) = ki=1 I(P (i) ).

Proof. Assume that C(G) is represented as the intersection of k matroids I1 ,. . . , Ik . Choose Ii arbitrarily (i ∈ {1, . . . , k}). Then the parallel elements of Ii
induce an equivalence relation on V . Let P (i) be the partition of V arising fromthis equivalence relation. Then the two-element circuits
T of Ii are the circuits ofI(P (i) ). Moreover, there is no loop in Ii (otherwise Ii cannot be a clique comSk
Skplex). Therefore, we have that min( i=1 C(Ii )) = min( i=1 C(I(P (i) ))), whichTk
Tkmeans that C(G) = i=1 Ii = i=1 I(P (i) ).
tuLemma 3.5. Let G = (V, E) be a graph and P be a partition of V . Then C(G) ⊆I(P) if and only if P is a stable-set partition of G.

Proof. Assume that P is a stable-set partition of G. Take I ∈ C(G) arbitrarily.
Then we have |I ∩ P | ≤ 1 for each P ∈ P by the definitions of cliques andstable sets. Hence I ∈ I(P), namely C(G) ⊆ I(P). Conversely, assume that
C(G) ⊆ I(P). Take P ∈ P and a clique C of G arbitrarily. From our assumption,
we have C ∈ I(P). Therefore, it holds that |C ∩ P | ≤ 1. This means that P is astable set of G, namely P is a stable-set partition of G.
tu
Now it is time to prove Theorem 3.3.
Proof (of Theorem 3.3). Assume that a given clique complex C(G) is represented
as the intersection of k matroids I1 , . . . , Ik . From Lemma 3.4, C(G) can be
represented as the intersection of k matroids associated with stable-set partitions
P (1) , . . . , P (k) of G. We will show that these partitions P (1) , . . . , P (k) satisfy thecondition in the statement of the theorem. By Lemma 3.1, {u, v} is an edge of G if
and only if {u, v} is a circuit of the clique complex C(G), namely {u, v} ∈ C(C(G))
SSS= min( ki=1 C(Ii )) = min( ki=1 C(I(P (i) ))) = ki=1 C(I(P (i) )). So this means

6

Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Unothat there exists at least one i ∈ {1, . . . , k} such that {u, v} ∈ C(I(P (i) )).
Hence, {u, v} ⊆ S for some S ∈ P (i) if and only if {u, v} is an edge of G.
Conversely, assume that we are given a family of stable-set partitions P (1) ,. . . , P (k) of V satisfying
the condition in the statement of the theorem. We will
Tk
show that C(G) = i=1 I(P (i) ). By Lemma 3.5, we can see that C(G) ⊆ I(P (i) )Tkfor all i ∈ {1, . . . , k}. This shows that C(G) ⊆ i=1 I(P (i) ). In order to show that
Tk
Sk
C(G) ⊇ i=1 I(P (i) ), we only have to show that C(C(G)) ⊆ i=1 C(I(P (I) )).
Take C ∈ C(C(G)) arbitrarily. By Lemma 3.1 we have |C| = 2. Set C = {u, v} ∈Sk
E(G). From our assumption, it follows that {u, v} ⊆ S for some S ∈ i=1 P (i) .
SkThis means that {u, v} ∈ i=1 C(I(P (i) )).
tu4

An Extremal Problem for a Clique Complex

Let µ(G) be the minimum number of matroids which we need for the representation of the clique complex of G as their intersection, and µ(n) be the maximum ofTkµ(G) over all graphs G with n vertices. Namely, µ(G) = min{k : C(G) = i=1 Ii
where I1 , . . . , Ik are matroids}, and µ(n) = max{µ(G) : G has n vertices}. In
this section,
 we will determine µ(n). From Lemma 2.2 we can immediately obtainµ(n) ≤ n2 . However, the following theorem tells us this is far from the truth.
Theorem 4.1. For every n ≥ 2, it holds that µ(n) = n − 1.

First we will prove that µ(n) ≥ n − 1. Consider the graph K1 ∪ Kn−1 .

K1 ∪ K 5
Lemma 4.2. For n ≥ 2, we have µ(K1 ∪ Kn−1 ) = n − 1, particularly µ(n) ≥n − 1.
Proof. K1 ∪ Kn−1 has n − 1 edges. From Lemma 3.1, the number of the circuitsof C(K1 ∪Kn−1 ) is n−1. By the argument below the proof of Lemma 2.2, we haveµ(K1 ∪Kn−1 ) ≤ n−1. Now, suppose that µ(K1 ∪Kn−1 ) ≤ n−2. By Theorem 3.3
and the pigeon hole principle, there exists a stable-set partition P of K1 ∪ Kn−1such that some class P in P contains at least two edges of K1 ∪ Kn−1 . However,this is impossible since P is stable. Hence, we have µ(K1 ∪ Kn−1 ) = n − 1. tuNext we will prove that µ(n) ≤ n − 1. To do that, first we will look at therelationship of µ(G) with the edge-chromatic number.
Lemma 4.3. We have µ(G) ≤ χ0 (G) for any graph G with n vertices. Particularly, if n is even we have µ(G) ≤ n − 1 and if n is odd we have µ(G) ≤ n.
Moreover, if µ(G) = n then n is odd and the maximum degree of G is n − 1 (i.e.,
G has an isolated vertex).

Matroid representation of clique complexes

7

Proof. Consider a minimum edge-coloring of G, and we will construct χ0 (G)stable-set partitions of a graph G with n vertices from this edge-coloring.
We have the color classes C (1) , . . . , C (k) of the edges where k = χ0 (G). Let us(i)(i)
take a color class C (i) = {e1 , . . . , eli } (i ∈ {1, . . . , k}) and construct a stableset partition P (i) of G from C (i) as follows: S is a member of P (i) if and only if(i)either (1) S is a two-element set belonging to C (i) (i.e., S = ej for somej ∈ {1, . . . , li }) or (2) S is a one-element set {v} which is not used in C (i) (i.e.,(i)v 6∈ ej for all j ∈ {1, . . . , li }). Notice that P (i) is actually a stable-set partition. Then we collect all the stable-set partitions P (1) , . . . , P (k) constructed by
the procedure above. Moreover, we can check that these stable-set partitions
satisfy the condition in Theorem 3.3. Hence, we have µ(G) ≤ k = χ0 (G).
Here, notice that χ0 (G) ≤ χ0 (Kn ). So if n is even, then χ0 (Kn ) is n − 1, whichconcludes µ(G) ≤ n−1. If n is odd, then χ0 (Kn ) is n, which concludes µ(G) ≤ n.
Assume that µ(G) = n. From the discussion above, n should be odd. Remarkthat Vizing’s theorem says for a graph H with maximum degree ∆(H) we have
χ0 (H) = ∆(H) or ∆(H)+1. If ∆(G) ≤ n−1, then we have that µ(G) ≤ χ0 (G) ≤∆(G) + 1 ≤ n. So µ(G) = n holds only if ∆(G) + 1 = n.
tu
Next we will show that if a graph G with an odd number of vertices has an
isolated vertex then µ(G) ≤ n − 1. This completes the proof of Theorem 4.1.
Lemma 4.4. Let n be odd and G be a graph with n vertices which has an isolated
vertex. Then µ(G) ≤ n − 1.
Proof. Let v ∗ be an isolated vertex of G. Consider the subgraph of G induced by
V (G) \ {v ∗ }. Call this induced subgraph G0 . Since G0 has n − 1 vertices, whichis even, we have µ(G0 ) ≤ n − 2 from Lemma 4.3.
Now we will construct n−1 stable-set partitions of G which satisfy the condition in Theorem 3.3 from n − 2 stable-set partitions of G0 which also satisfy thecondition in Theorem 3.3. Denote the vertices of G0 by 1, . . . , n − 1, and the
(1)
(n−2)
stable-set partitions of G0 by P 0 , . . . , P 0. Then construct stable-set par(1)
(n−2)
(n−1)
titions P , . . . , P,Pof G as follows. For i = 1, . . . , n − 2, S ∈ P (i)(i)(i)
if and only if either (1) S ∈ P 0 and i 6∈ S or (2) v ∗ ∈ S, S \ {v ∗ } ∈ P 0 and(n−1)∗
i ∈ S. Also S ∈ P
if and only if either (1) S = {v , n − 1} or (2) S = {i}(i = 1, . . . , n−2). We can observe that the stable-set partitions P (1) , . . . , P (n−1)
satisfy the condition in Theorem 3.3 since v ∗ is an isolated vertex of G.
tu

5Characterization for Two Matroids

In this section, we will look more closely at a clique complex which can be represented as the intersection of two matroids. Note that Fekete–Firla–Spille [5]gave a characterization of the graphs whose matching complexes can be represented as the intersections of two matroids. So the theorem in this section is a
generalization of their result.

8

Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno

To do this, we introduce another concept. The stable-set graph of a graph
G = (V, E) is a graph whose vertices are the maximal stable sets of G and two
vertices of which are adjacent if the corresponding two maximal stable sets sharea vertex in G. We denote the stable-set graph of a graph G by S(G).
Lemma 5.1. Let G be a graph. Then the clique complex C(G) can be represented
as the intersection of k matroids if the stable-set graph S(G) is k-colorable.
Proof. Assume that we are given a k-coloring c of S(G). Then gather the maximal stable sets of G which have the same color with respect to c, that is, put
Ci = {S ∈ V (S(G)) : c(S) = i} for all i = 1, . . . , k. We can see that the membersof Ci are disjoint maximal stable sets of G for each i.
Now we construct a graph Gi from Ci as follows. The vertex set of Gi is thesame as that of G, and two vertices of Gi are adjacent if and only if either (1) one
belongs to a maximal stable set in Ci and the other belongs to another maximal
stable set in Ci , or (2) one belongs to a maximal stable set in Ci and the otherbelongs to no maximal stable set in Ci . Remark that Gi is complete r-partite,where r is equal to |Ci | plus the number of the vertices which do not belong to
any maximal stable set in Ci . Then consider C(Gi ), the clique complex of Gi .
By Lemma 3.2, we can see that C(Gi ) is actually a matroid. Since an edge of G
is also an edge of Gi , we have that C(G) ⊆ C(Gi ).
Tk
Here we consider the intersection I = i=1 C(Gi ). Since C(G) ⊆ C(Gi ) for
any i, we have C(G) ⊆ I. Since each circuit of C(G) is also a circuit of C(Gi )for some i (recall Lemma 3.1), we also have C(C(G)) ⊆ C(I), which implies
C(G) ⊇ I. Thus we have C(G) = I.
tu
Note that the converse of Lemma 5.1 does not hold even if k = 3. A
counterexample is the graph G = (V, E) defined as V = {1, 2, 3, 4, 5, 6} andE = {{1, 2}, {3, 4}, {5, 6}}. Here C(G) is represented as the intersection of threematroids C(I1 ) = {{1, 3, 5}, {2, 4, 6}}, C(I2 ) = {{1, 3, 6}, {2, 4, 5}} and C(I3 ) ={{1, 4, 5}, {2, 3, 6}} while S(G) is not 3-colorable but 4-colorable.
However, the converse holds if k = 2.
Theorem 5.2. Let G be a graph. The clique complex C(G) can be represented
as the intersection of two matroids if and only if the stable-set graph S(G) is
2-colorable (i.e., bipartite).
Proof. The if-part is straightforward from Lemma 5.1. We will show the onlyif-part. Assume that C(G) is represented as the intersection of two matroids.
Thanks to Theorem 3.3, we assume that these two matroids are associated withstable-set partitions P (1) , P (2) of G satisfying the condition in Theorem 3.3.
Let S be a maximal stable set of G. Now we will see that S ∈ P (1) ∪P (2) . Fromthe maximality of S, we only have to show that S ⊆ P for some P ∈ P (1) ∪ P (2) .
(Then, the maximality of S will tell us that S = P .) This claim clearly holds if|S| = 1. If |S| = 2, the claim holds from the condition in Theorem 3.3.
Assume that |S| ≥ 3. Consider the following independence system I = {I ⊆S : I ⊆ P for some P ∈ P (1) ∪P (2) }. Take a base B of I arbitrarily. Since B ⊆ S,

Matroid representation of clique complexes

9

B is a dependent set of C(G). So B contains a circuit of C(G). By Lemma 3.1,
we have |B| ≥ 2. Suppose that S \ B 6= ∅ for a contradiction. Pick up u ∈ S \ B.
Assume that B ⊆ P for some P ∈ P (1) , without loss of generality. Then {u, v}
is a circuit of C(G) for any v ∈ B since S is a stable set of G. Moreover, u andv belong to different sets of P (1) (otherwise, it would violate the maximality of
B). From the condition in Theorem 3.3, there should exist some P 0 ∈ P (2) suchthat {u, v} ⊆ P 0 for all v ∈ B. By the transitivity of the equivalence relationinduced by P (2) , we have {u} ∪ B ⊆ P 0 . This contradicts the maximality of B.
Therefore, we have S = B, which means that S ∈ P (1) ∪ P (2) .
Now we color the vertices of S(G), i.e., the maximal stable sets of G. If amaximal stable set S belongs to P (1) , then S is colored by 1. Similarly if S
belongs to P (2) , then S is colored by 2. (If S belongs to both, then S is coloredby either 1 or 2 arbitrarily.) This coloring certainly provides a proper 2-coloringof S(G) since P (1) and P (2) are stable-set partitions of G.
tuSome researchers already noticed that the bipartiteness of S(G) is characterized by other properties. We gather them in the following proposition.
Proposition 5.3. Let G be a graph. Then the following are equivalent. (1) The
stable-set graph S(G) is bipartite. (2) G is the complement of the line graph ofa bipartite multigraph. (3) G has no induced subgraph isomorphic to K 1 ∪ K3 ,K1 ∪ K2 ∪ K2 , K1 ∪ P3 or C2k+3 (k = 1, 2, . . . ).

K1 ∪ K 3

K1 ∪ K 2 ∪ K 2

K1 ∪ P 3

Proof. “(1) ⇔ (2)” is immediate from a result by Cai–Corneil–Proskurowski [1].
Also “(1) ⇔ (3)” is immediate from a result by Protti–Szwarcfiter [12].
tuFrom the view of Proposition 5.3, we can decide whether the stable-set graphof a graph is bipartite or not in polynomial time using the algorithm describedby Protti–Szwarcfiter [12].

6Concluding Remarks

In this paper, motivated by the quality of a natural greedy algorithm for the
maximum weighted clique problem, we characterized the number k such that theclique complex of a graph can be represented as the intersection of k matroids(Theorem 3.3). This implies that the problem to determine the clique complex
of a given graph has a representation by k matroids or not belongs to NP. Also,in Sect. 5 we observed that the corresponding problem for two matroids can besolved in polynomial time. However, the problem for three or more matroids
is not known to be solved in polynomial time. We leave the further issue on
computational complexity of this problem as an open problem.
Moreover, we showed that n − 1 is exactly the maximum number of matroids
we need for the representation of the clique complex of a graph with n vertices

10Kenji Kashiwabara, Yoshio Okamoto, and Takeaki Uno(Theorem 4.1). This implies that the approximation ratio of the greedy algorithm
for the maximum weighted clique problems is at most n − 1.
Furthermore, we can show the following theorem. In this theorem, we see
a graph itself as an independence system: namely a subset of the vertex set isindependent if and only if it is (1) the empty set, (2) a one-element set, or (3)a two-element set which forms an edge of the graph. A proof is omitted due tothe page limitation.
Theorem 6.1. A graph G can be represented as the intersection of k matroids
if and only if the clique complex C(G) can be represented as the intersection of
k matroids.
In this paper, we approached the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. This approach might be useful for other combinatorial optimization problems.

Acknowledgements
The authors thank Emo Welzl for suggesting the problem discussed in Sect. 4
and anonymous referees for useful comments.

References
1. L. Cai, D. Corneil and A. Proskurowski: A generalization of line graphs: (X, Y )intersection graphs. Journal of Graph Theory 21 (1996) 267–287.
2. R. Diestel: Graph Theory (2nd Edition). Springer Verlag, New York, 2000.
3. J. Edmonds: Matroids and the greedy algorithm. Mathematical Programming 1(1971) 127–136.
4. U. Faigle: Matroids in combinatorial optimization. In: Combinatorial Geometries(N. White, ed.), Cambridge University Press, Cambridge, 1987, pp. 161–210.
5. S.P. Fekete, R.T. Firla and B. Spille: Characterizing matchings as the intersectionof matroids. Preprint, December 2002, arXiv:math.CO/0212235.
6. A. Frank: A weighted matroid intersection algorithm. Journal of Algorithms 2(1981) 328–336.
7. T.A. Jenkyns: The efficacy of the “greedy” algorithm. Proceedings of the 7thSoutheastern Conference on Combinatorics, Graph Theory, and Computing, Utilitas Mathematica, Winnipeg, 1976, pp. 341–350.
8. B. Korte and D. Hausmann: An analysis of the greedy algorithm for independence
systems. In: Algorithmic Aspects of Combinatorics; Annals of Discrete Mathematics 2 (B. Alspach et al., eds.), North-Holland, Amsterdam, 1978, pp. 65–74.
9. B. Korte and J. Vygen: Combinatorial Optimization (2nd Edition). Springer Verlag, Berlin Heidelberg, 2002.
10. Y. Okamoto: Submodularity of some classes of the combinatorial optimization
games. Mathematical Methods of Operations Research, to appear.
11. J. Oxley: Matroid Theory. Oxford University Press, New York, 1992.
12. F. Protti and J.L. Szwarcfiter: Clique-inverse graphs of bipartite graphs. Journalof Combinatorial Mathematics and Combinatorial Computing 40 (2002), 193–203.
13. R. Rado: Note on independence functions. Proceedings of the London Mathematical Society 7 (1957) 300–320.