arXiv:1210.1336v1 [] 4 Oct 2012

COHEN-MACAULAY r-PARTITE GRAPHS WITH
MINIMAL CLIQUE COVER
ASGHAR MADADI, RASHID ZAARE-NAHANDI
Abstract. In this note, we give some necessary conditions for an
r-partite graph such that the edge ring of the graph is CohenMacaulay. It is proved that if G is an r-partite Cohen-Macaulay
graph which is covered by some disjoint cliques of size r, then the
clique cover is unique.

1. Introduction
Mainly, after using the notion of simplicial complexes and its algebraic interpretation by R. Stanley in 1970s to prove the upper bound
conjecture for number of simplicial spheres [8], this notion has been
one of the main streams of research in commutative algebra. In this
stream, characterization and classification of Cohen-Macaulay simplicial complexes have been extensively studied in the last decades. It is
known that Cohen-Macaulay property of a simplicial complex and its
level graph are coincide. Therefore, to characterize all simplicial complexes which are Cohen-Macaulay, is enough to characterize all graphs
with this property [8].
To examine special classes of graphs, Estrada and Villarreal in [3]
found some necessary conditions for bipartite graphs to be Cohen-Macaulay.
Finally, Herzog and Hibi in [4] presented a combinatorial characterization for bipartite graphs equivalent to Cohen-Macaulay property of these
graphs. This purely combinatorial method can not be generalized for
r-partite graphs in general. Because, as shown in Example 2.3, CohenMacaulay property may depend on characteristics of the base field. In
other hand, it is shown in [11], the corresponding graph to a simplicial
complex, such that has the same Cohen-Macaulayness property is covered by minimal possible number of cliques. In this paper, we consider
2010 Mathematics Subject Classification. 05C25, 05E40, 05E45, 13F55.
Key words and phrases. Cohen-Macaulay graph, r-partite, clique cover, perfect
r-matching.
1

2

A. MADADI, R. ZAARE-NAHANDI

r-partite graphs with a minimal clique cover and find a necessary condition for Cohen-Macaualayness of these graphs. More precisely, we prove
that in a Cohen-Macaulay r-partite graph with a minimal clique cover,
there is a vertex of degree r − 1 and the cover is unique.
2. Preliminaries
A simple graph is an undirected graph that has no loop and multiple
edge. A finite graph is denoted by G = (V (G), E(G)), where V (G) is
the set of vertices and E(G) is the set of edges. Let |V (G)| = n. We
use [n] = {1, 2, . . . , n} as vertices of G. The complementary graph of G
is the graph Ḡ on [n] whose edge set E(Ḡ) consists of those edges {i, j}
which are not in E(G). An independent set of vertices is a set of pairwise
nonadjacent vertices. An r-partite graph is a graph that the set of its
vertices can be partitioned into r disjoint subsets such that each set is
independent. A subset A ⊂ [n] is a minimal vertex cover of G if (i) each
edge of G is incident with at least one vertex in A, and (ii) there is no
proper subset of A with property (i). It is easy to check that any minimal
vertex cover of a graph is complement set of a maximal independent set
of the graph. A graph G is called unmixed (well-covered) if any two
minimal vertex covers of G have the same cardinality. A clique in a
graph is a set of pairwise adjacent vertices, and by a r-clique we mean a
clique of size r. An r-matching is a set of pairwise disjoint r-cliques and
a perfect r-matching is an r-matching which covers all vertices of G.
Let ω(G) denote the maximum size of cliques in G, which is called
clique number of G. Let f : V (G) → [k] be a map such that if v1 is
adjacent to v2 then f (v1 ) 6= f (v2 ). If such a map exists, we say that
G is colorable by k colors. The smallest such k is called chromatic
number of the graph and is denoted by χ(G). A graph G is called
perfect if ω(H) = χ(H) for each induced subgraph H of G. The class
of perfect graphs plays an important role in graph theory and most of
computations in this class can be done by fast algorithms. L. Lovász
in [7] has proved that a graph is perfect if and only if its complement
is perfect. Chudnovsky et al in [2] have proved that a necessary and
sufficient condition for a graph G to be perfect is that G does not have
an odd hole (a cycle of odd length greater than 3) or an odd antihole
(complement of an odd hole) as induced subgraph.
Let G be a graph on [n]. Let S = K[x1 , . . . , xn ], the polynomial ring
over a field K. The edge ideal I(G) of G is defined to be the ideal of S
generated by all square-free monomials xi xj provided that i is adjacent

COHEN-MACAULAY r-PARTITE GRAPHS WITH MINIMAL CLIQUE COVER

3

to j in G. The quotient ring R(G) = S/I(G) is called the edge ring of
G.
Let R be a commutative ring with an identity. The depth of R,
denoted by depth(R), is the largest integer r such that there is a sequence f1 , . . . , fr of elements of R such that fi is not a zero-divisor in
R/(f1 , . . . , fi−1 ) for all 1 ≤ i ≤ r, and (f1 , . . . , fr ) 6= R. Such a sequence
is a called a regular sequence. The depth is an important invariant of
a ring. It is bounded by another important invariant, the Krull dimension, the length of the longest chain of prime ideals in the ring. A ring
R is called Cohen-Macaulay if depth(R) = dim(R). A graph G is called
Cohen-Macaulay if the ring R(G) is Cohen-Macaulay.
Theorem 2.1. [9, Proposition 6.1.21] If G is a Cohen-Macaulay graph,
then G is unmixed.
A simplicial complex ∆ on n vertices is a collection of subsets of [n]
such that the following conditions hold:
(i) {i} ∈ ∆ for each i ∈ [n],
(ii) if E ∈ ∆ and F ⊆ E then F ∈ ∆.
An element of ∆ is called a face and a maximal face with respect to
inclusion is called a facet. The set of all facets of ∆ is denoted by F(∆).
The dimension of a face F ∈ ∆ is defined to be |F | − 1 and dimension of
∆ is maximum of dimension of its faces. A simplicial complex is called
pure if all of its facets have the same dimension. For more details on
simplicial complexes see [8].
The clique complex of a finite graph G on [n] is the simplicial complex
∆(G) on [n] whose faces are the cliques of G. Let ∆ be a simplicial
complex on [n]. We say that ∆ is shellable if its facets can be ordered as
F1 , F2 , . . . , Fm such that for all j ≥ 2 the subcomplex (F1 , . . . , Fj−1 )∩ Fj
is pure of dimension dimFj − 1. An order of the facets satisfying this
condition is called a shelling order. To say that F1 , F2 , . . . , Fm is a
shelling order of ∆ is equivalent to say that for all i, 2 ≤ i ≤ m and all
j < i, there exists l ∈ Fi \ Fj and k < i such that Fi \ Fk = {l}. G is
called shellable if ∆(Ḡ) has this property.
Let ∆ be a simplicial complex on [n] and I∆ be the ideal of S =
K[x1 , . . . , xn ] generated by all square-free monomials xi1 · · · xit , provided
that {i1 , . . . , it } is not a face of ∆. The ring S/I∆ is called the StanleyReisner ring of ∆. A simplicial complex is called Cohen-Macaulay if its
Stanley-Reisner ring is Cohen-Macaulay.

4

A. MADADI, R. ZAARE-NAHANDI

4
7

1
5
2

10

11
8

6
3

9

Figure 1. Cohen-Macaulay property depends on characteristic
Theorem 2.2. [5, Theorem 8.2.6] If ∆ is a pure and shellable simplicial
complex, then ∆ is Cohen-Macaulay.
M. Estrada and R. H. Villarreal in [3] have proved that for a bipartite
graph G Cohen-Macaulayness and pure shellability are equivalent. This
is not true in general for r-partite graphs when r > 2 (Example 2.3).
Also in bipartite graphs, Cohen-Macaulayness does not depend on
characteristics of the ground field. But again, this is not true in general
as shown in the following example.
Example 2.3. Let G be the graph in Figure 1. Then, R(G) is CohenMacaulay when the characteristic of the ground field K is zero but it is
not Cohen-Macaulay in characteristic 2. Therefore the graph G is not
shellable ([6]).
3. Cohen-Macaulay property and uniqueness of perfect
r-matching
M. Estrada and R. H. Villarreal in [3] have proved that if G is a
Cohen-Macaulay bipartite graph and has at least one vertex of positive
degree, then there is a vertex v such that deg(v) = 1. By deg(v) we
mean the number of vertices adjacent to v. J. Herzog and T. Hibi in [4]
have proved that a bipartite graph G with parts V1 and V2 is CohenMacaulay if and only if, |V1 | = |V2 | and there is an order on the vertices
of V and W as v1 , . . . , vn and w1 , . . . , wn respectively, such that:
1) vi ∼ wi for i = 1, . . . , n,
2) if vi ∼ wj , then i ≤ j,
3) for each 1 ≤ i < j < k ≤ n if vi ∼ wj and vj ∼ wk , then vi ∼ wk .

COHEN-MACAULAY r-PARTITE GRAPHS WITH MINIMAL CLIQUE COVER

5

R. Zaare-Nahandi in [10] has proved that a well-covered bipartite
graph G is Cohen-Macaulay if and only if there is a unique perfect 2matching in G.
Let α(G) denote the maximum cardinality of independent sets of vertices of G. Let G be the class of graphs such that for each G ∈ G there
are k = α(G) cliques in G covering all its vertices. For each G ∈ G and
cliques Q1 , . . . , Qk such that V (Q1 ) ∪ · · · ∪ V (Qk ) = V (G), we may take
Q′ 1 = Q1 and for i = 2, . . . , k, Q′ i the induced subgraph on the vertices
V (Qi )\(V (Q1 )∪ · · · ∪ V (Qi−1 )). Then Q′ 1 , . . . , Q′ k are k disjoint cliques
covering all vertices of G. We call such a set of cliques, a basic clique
cover of the graph G. Therefore any graph in the class G has a basic
clique cover.
Proposition 3.1. Let G be an r-partite, unmixed and perfect graph such
that all maximal cliques are of size r. Then G is in the class G.
Proof. Let V1 , . . . , Vr be parts of G. By [11], |V1 | = |V2 | = · · · = |Vr | =
α(G). Also by [7], the complement graph Ḡ is perfect. In other hand,
Vi is a clique of maximal size in Ḡ for each 1 ≤ i ≤ r. Therefore,
χ(Ḡ) = ω(Ḡ) = α(G). This implies that Ḡ is α(G)-partite. Therefore
there are α(G) disjoint maximal cliques in G covering all vertices.

The converse of the above proposition is not true in the sense of the
following example.
Example 3.2. Let G be the graph in Figure 2. Then G is a graph in
class G which is 4-partite, unmixed and all maximal cliques are of size
4. But the induced subgraph on {A, B, C, D, E} is a cycle of length 5
and therefore, by [2], the graph G is not perfect.
Let H be a graph and v be a vertex of H. Let N (v) be the set of all
vertices of H adjacent to v.
Theorem 3.3. [9, Proposition 6.2.4] If H is Cohen-Macaulay and v is
a vertex of H, then H \ (v, N (v)) is Cohen-Macaulay.
Theorem 3.4. [11] Let G be an r-partite unmixed graph such that all
maximal cliques are of size r. Then all parts have the same cardinality
and there is a perfect 2-matching between each two parts.
Now, we present the main theorem of this paper which is generalization of [3, Theorem 2.4].

6

A. MADADI, R. ZAARE-NAHANDI

A

B

C

E

D

Figure 2. A graph in class G which is not perfect
Theorem 3.5. Let G be an r-partite graph in the class G such that
each maximal clique is of size r. If G is Cohen-Macaulay then there is
a vertex of degree r − 1 in G.
Proof. By Theorem 3.4 all parts have the same cardinality. So there is a
positive integer n such that |V | = rn. Assume that for all vertices v in
G we have deg(v) ≥ r. Let Qi = {x1i , x2i , . . . , xri } for i = 1, . . . , n are
cliques in a basic clique cover of G. Without loss of generality, assume
that v11 be a vertex of the minimal degree. If deg(v11 ) = (r − 1)n then
G = Kn,n,...,n is a complete r−partite graph. Thus G is not CohenMacaulay by [1, Exercise 5.1.26] and we get a contradiction. Therefore,
r ≤ deg(v11 ) ≤ (r − 1)n − 1.
Let N (v11 ) = {v21 , . . . , v2l2 , v31 , . . . , v3l3 , . . . , vr1 , . . . , vrlr }. We have
deg(v11 ) = l2 + · · · + lr . Without loss of generality, we may assume that
l2 ≤ li for i = 3, . . . , r. Set G′ = G \ ({v11 }, N (v11 )). The graph G′ is
Cohen-Macaulay by Theorem 2.1. If l2 = 1, then, there exists 3 ≤ i ≤ r
such that li ≥ 2. The sets
\
{v12 , . . . , v1n , v22 , . . . , v2n , v3(l3 +1) , . . . , v3n , . . . , (vi(li +1)
, . . . , vin ), . . . ,
vr(lr +1) , . . . , vrn }
and
{v12 , . . . , v1n , v3(l3 +1) , . . . , v3n , . . . , vi(li +1) , . . . , vin , . . . , vr(lr +1) , . . . , vrn }
are two minimal vertex covers for G′ and their cardinalities are not
\
equal. Here, by (vi(li +1)
, . . . , vin ) we mean the vertices vi(li +1) , . . . , vin
are removed from the set. This contradicts to Cohen-Macaulayness of

COHEN-MACAULAY r-PARTITE GRAPHS WITH MINIMAL CLIQUE COVER

7

G′ . Therefore, l2 ≥ 2. We claim that
deg(v1i ) = l2 + l3 + · · · + lr = deg(v11 ),

i = 1, . . . , l2 .

It is enough to show that deg(v12 ) = l2 + l3 + · · · + lr and analogous
argument proves the claim. If deg(v12 ) > l2 + l3 + · · · + lr , then there is
a jt , lt + 1 ≤ jt ≤ n for some 2 ≤ t ≤ r, such that v12 ∼ vtjt . Without
loss of generality we assume that t = 2.
If there is j2 , l2 + 1 ≤ j2 ≤ n, such that v12 ∼ v2j2 then there is a
minimal vertex cover for G′ containing the set
{v12 , v1(l2 +1) , . . . , v1n , v3(l3 +1) , . . . , v3n , . . . , vr(lr +1) , . . . , vrn }.
In other hand, {v2(l2 +1) , . . . , v2n , . . . , vr(lr +1) , . . . , vrn } is a minimal vertex cover of G′ . By l2 ≥ 2 and Theorem 2.1, this contradicts CohenMacaulayness of G′ . Therefore deg(v12 ) = l2 + l3 + · · · + lr . Thus, for all
1 ≤ i ≤ l2 we have N (v1i ) = {v21 , . . . , v2l2 , v31 , . . . , v3l3 , . . . , vr1 , . . . , vrlr }.
Consider the graph H = G \ {v2(l2 +1) , . . . , v2n , . . . , vr(lr +1) , . . . , vrn } ∪

N (v2(l2 +1) ) ∪ · · · ∪ N (v2n ) ∪ · · · ∪ N (vr(lr +1) ) ∪ · · · ∪ N (vrn ) . By Theorem
3.3, H is Cohen-Macaulay but the complement of H is not connected.

This is a contradiction by [1, Exercise 5.1.26].
Theorem 3.5 implies that the perfect r-matching in a Cohen-Macaulay
r-partite graph is unique.
Corollary 3.6. Let G be an r-partite graph in the class G such that all
maximal cliques are of size r. If G is Cohen-Macaulay then there is a
unique perfect r-matching in G.
Proof. Since G is in the class G, there is a perfect r-matching in G. By
Theorem 3.5, there is a vertex x ∈ V (G) of degree r − 1. Therefore,
the r-clique in the r-matching which contains x, must be in all perfect
r-matchings of G. The graph G \ ({x, N (x)}) is again an r-partite graph
in the class G which is Cohen-Macaulay by Theorem 3.3. Continuing
this process, we find that the chosen perfect r-matching is the unique
perfect r-matching in G.

References
[1] W. Bruns and J. Herzog, Cohen-Macaulay Rings, Cambridge University Press,
1998.
[2] M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas, The strong perfect
graph theorem, Ann. of Math., 164 (2006), no. 1, 51–229.
[3] M. Estrada and R. H. Villarreal, Cohen-Macaulay bipatite graphs, Arc. Math.,
68 (1997), no. 2, 124-128.

8

A. MADADI, R. ZAARE-NAHANDI

[4] J. Herzog and T. Hibi, Distributive lattices, bipartite graphs, and Alexander
duality, J. Algebraic Combin., 22 (2005), no. 3, 289-302.
[5] J. Herzog and T. Hibi, Monomial Ideals, Springer-Verlag, 2011.
[6] M. Katzman, Characteristic-independence of Betti numbers of graph ideals, J.
Combin. Theory, Series A 113 (2006), no. 3, 435–454.
[7] L. Lovász, A Characterization of Perfect Graphs, J. Combin. Theory, Series B
13 (1972), 95-98.
[8] R. Stanley, Combinatorics and Commutative Algebra, 2nd Ed., Progress in
Math., Birkhauser, 1996.
[9] R. H. Villarreal, Monomial Algebras, Marcel Dekker, 2001.
[10] R. Zaare-Nahandi, Cohen-Macauleyness of bi-partite graphs: revisited, Preprint.
arxiv:1012.0457v2 []
[11] R. Zaare-Nahandi, Pure simplicial complexes and well-covered graphs, Preprint.
arxiv: 1104.4556v2 []
Asghar Madadi, Department of Mathematics, Faculty of Sciences, University of Zanjan, P. O. Box 45195-313, Zanjan, Iran
E-mail address: a madadi@znu.ac.ir
Rashid Zaare-Nahandi, Department of Mathematics, Institute for Advanced Studies in Basic Sciences, P. O. Box 45195-1159, Zanjan, Iran
E-mail address: rashidzn@iasbs.ac.ir

