Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 36 (1995), No. 1, 89-96.

Gröbner Bases and Graph Colorings*

Jesús A. de Loera

Center for Applied Mathematics,Cornell University 657 Theory Center, Ithaca N.Y. 14853-6201, U.S.A E-mail: jdl@cam.cornell.edu

Abstract. We explore applications of computational methods in commutative algebra to graph theory. We give an explicit universal Gröbner basis for the radical ideal of a family of linear subspace arrangements related to chromatic numbers. We describe how to apply Gröbner bases to enumerate colorings. We also discuss similar results for a family of zero dimensional ideals.

1. Introduction

We are interested in a family of algebraic varieties, whose elements are equi-dimensional unions of linear subspaces in K^{n}. Here K is any field. Let V (n, k) ⊆ K^{n} denote the set of vectors which have at most k − 1 distinct coordinates. V (n, k) is the union of S(n, k − 1) (this denotes the Stirling number of the second kind) linear subspaces of dimension k − 1, hence it is an algebraic variety and we write J(n, k) ⊆ K[x_{1}, ..., x_{n}] for its vanishing ideal. Extending a result of Kleitman and Lovász (see [12, 13]) we prove the following theorem:

Theorem 1.1 The set of polynomials, ρ(n, k) = {∏_{1≤r<s≤k}(x_{i_{r}} −x_{i_{s}})|1 ≤ i_{1} < ... < i_{k} ≤ n} is a universal Gröbner basis for the ideal J(n, k).

The above algebraic theorem is related to graph theory through the following definition. With any labeled graph G on the set of vertices V = {x_{1}, ..., x_{n}} we associate the polynomial

P_{G} = ∏_{i<j,x_{i}x_{j}∈E(G)}(x_{i} − x_{j}).

We can thus reformulate Theorem 1.1 as follows. The polynomials P_{H}, where H is a graph consisting of a clique of size k and n − k isolated vertices, form a universal Gröbner basis for the ideal J(n, k).

* Research supported by the National University of México through a doctoral fellowship

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1995 Heldermann Verlag, Berlin

A graph G is k-colorable if k colors are sufficient to color its vertices in such a way that no two vertices of the same color are adjacent. We remark that a graph G is not (k − 1) − colorable if and only if the polynomial P_{G} vanishes when we identify its variables in such a way that at most k − 1 distinct variables remain. From Theorem 1.1 we have:

Corollary 1.2 Let G be a graph with n vertices. The graph G is not (k − 1)-colorable if and only if P_{G} belongs to J(n, k). Furthermore, this happens if and only if the normal form of P_{G}, obtained by the division algorithm using ρ(n, k), is zero.

In section two we present the proof of Theorem 1.1. Section three contains examples and a result concerning the number of distinct of colorings in a graph. The final section presents a similar application of Gröbner bases theory to a family of zero dimensional ideals.

2. A universal Gröbner basis

A Gröbner basis for an ideal I is a set of generators with additional computational properties. Through their use many questions about general ideals in polynomial rings can be reduced to questions about ideals generated by monomials, which are far easier. Gröbner bases have developed into a central tool of computational algebraic geometry and commutative algebra. We briefly state the necessary definitions and results from Gröbner bases theory, for a detailed introduction see [6] and [9].

A total order ⪯ on the monomials of K[x_{1}, ..., x_{n}] is said to be admissible if 1 ⪯ m_{1} for all monomial m_{1} and m_{1} ⪯ m_{2} implies m_{1}m_{3} ⪯ m_{2}m_{3} for all monomials m_{1}, m_{2}, m_{3} in K[x_{1}, ..., x_{n}]. The lexicographic order is an important example of admissible monomial order. The leading monomial of a polynomial f in K[x_{1}, ..., x_{n}] with respect to ⪯ will be denoted by in_{⪯}(f). For an ideal I contained in K[x_{1}, .., x_{n}] its leading ideal is the ideal in_{⪯}(I) generated by the leading monomials of all polynomials in I. The monomials m ∉ in_{⪯}(I) are called standard. A finite subset of polynomials G = {g_{1}, ..., g_{n}} of I is a Gröbner basis of I with respect to ⪯ if in_{⪯}(I) is generated by {in_{⪯}(g_{1}), ..., in_{⪯}(g_{n})}. In other words G is a Gröbner basis for I if the leading monomial of any polynomial in I is divisible by one of the monomials in_{⪯}(g_{i}). It can be proved from the definition that a Gröbner basis is a generating set for the ideal I. A universal Gröbner basis of I is a finite subset of I which is a Gröbner basis simultaneously with respect to any admissible monomial order. In the rest of the article all monomial orders are considered to be admissible.

Given an ideal I and any monomial order ⪯, it is known that the set of standard monomials forms a K-vector space basis for the residue ring K[x_{1}, ..., x_{n}]/I. Gröbner bases theory provides a division algorithm for computing the residue or normal form of a polynomial f modulo I. First compute a Gröbner basis G for I with respect to ⪯. Iterate the following process: Check whether all monomials in f are standard. If so, we have a normal form for f. Otherwise consider the highest non-standard monomial m in f. Find g ∈ G such that in_{⪯}(g) divides m, thus for some monomial q we have m = in(g)q. Replace f by f − gq. Repeat this process until all monomials in f are standard (this will happen eventually). We remark that the normal form obtained by the division algorithm using the Gröbner basis is unique. One can prove that f belongs to I if and only if the normal form of f is zero. Several computer algebra systems such as MACAULAY,MAPLE and MATHEMATICA contain implementations of algorithms for finding a Gröbner basis of a set of polynomials, computing the normal form of a polynomial and other applications of Gröbner bases. Gröbner bases can be used, for example, to compute generators for ideal intersections, algebraic relations of a set of polynomials, dimension and degree of algebraic varieties and testing solvability of polynomial systems of equations.

Lemma 2.1 Let F = {f_{1}, f_{2}, ..., f_{k}} be a set of polynomials in K[x_{1}, ..., x_{n}] such that each polynomial f_{i} is a product of linear factors and for any permutation π of {1, ..., n} we have π(f_{i}(x_{1}, ..., x_{n})) = f_{i}(x_{π(1)}, ..., x_{π(n)}) ∈ F. If F is a Gröbner basis for the ideal ⟨F ⟩ with respect to the lexicographic monomial order induced by x_{1} > x_{2} > ... > x_{n} then F is a universal Gröbner basis for the ideal ⟨F ⟩.

Proof: Let > be any other monomial order which satisfies x_{1} > x_{2} > ... > x_{n}. We know f_{i} = l_{1i}l_{2i}..l_{k_{i}i}, where l_{jk} is a linear form a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}+a_{n+1}. We also know that in_{>}(f_{i}) = in_{>}(l_{1i})in_{>}(l_{2i})..in_{>}(l_{k_{i}i}). On the other hand in_{>}(a_{1}x_{1}+a_{2}x_{2}+...+a_{n}x_{n}+a_{n+1}) is equal to in_{lex}(a_{1}x_{1} + a_{2}x_{2} + ... + a_{n}x_{n} + a_{n+1}) because for both monomial orders x_{1} > x_{2} > ... > x_{n}. As a consequence both > and lex select the same leading monomials. F is a Gröbner basis with respect to > also. If ⪰ is a monomial order with x_{i_{1}} ⪰ x_{i_{2}} ⪰ ... ⪰ x_{i_{n}}, then ⪰ is induced from a corresponding monomial order with x_{1} > x_{2} > ... > x_{n} using a permutation π of the variables. Since F is invariant under the action of permutations, the set F is a Gröbner basis with respect to ⪰. This proves the lemma.

Proof of Theorem 1.1: The elements of ρ(n, k) are in bijection with the k element subsets of {x_{1}, ..., x_{n}}. They satisfy the hypothesis of Lemma 2.1. It is enough to prove that ρ(n, k) is a Gröbner basis for the lexicographic order induced by x_{1} > ... > x_{n}. We use in for in_{lex} in the following.

We proceed by a double induction on k and n. Let k = 2 and n arbitrary. Let f be an element of J(n, 2). We know that ρ(n, 2) is just {(x_{i} − x_{j})|1 ≤ i < j ≤ n} and then in(ρ(n, 2)) = {x_{1}, ..., x_{n−1}}. If in(f) contains any of the first n − 1 variables, then in(f) ∈ ⟨(ρ(n, 2))⟩. Otherwise we have in(f) = x_{n}^{s}. This would imply that f is a polynomial on x_{n}, since we are using the lexicographic monomial order, but no nonzero univariate polynomial belongs to J(n, 2). This settles the result for J(n, 2) for all n.

By induction on k the result is true for J(n, q) where k > q ≥ 2 and n arbitrary. We proceed by induction on n to prove the result for J(n, k). We observe that J(k, k) is the principal ideal generated by the polynomial ∏_{1≤i<j≤k}(x_{i} −x_{j}); this settles the case n = k. Now by induction hypothesis the result is true for J(p, k) with n > p ≥ k. Let f be a polynomial in J(n, k), we want to prove that in(f) belongs to the ideal ⟨in(ρ(n, k))⟩. To do this we construct an auxiliary polynomial. Given S ⊆ {1, ..., n − 1}, we denote by f_{S} the polynomial obtained from f by substituting x_{n} for each variable x_{i}, i ∈ S. We observe that for a non-empty S the polynomial f_{S} belongs to J(p, k) with n > p ≥ k. Now we define g as follows:

g = ∑_{S⊆{1,...,n−1}}(−1)^{|S|}f_{S}.

We claim that in(g) belongs to ⟨in(ρ(n, k))⟩. If we substitute x_{n} for any x_{i} with 1 ≤ i ≤ n − 1 we get the zero polynomial. Therefore g is divisible by the product (x_{1}−x_{n})(x_{2}−x_{n})...(x_{n−1}−x_{n}), thus we can write it as g = (x_{1}−x_{n})(x_{2}−x_{n})...(x_{n−1}−x_{n})h. Since g belongs to J(n, k), if we expand h as a polynomial in x_{n}, its coefficients L_{i} belong to J(n − 1, k − 1). By the induction hypothesis in(L_{i}) belongs to ⟨in(ρ(n − 1, k − 1))⟩. We observe that in(h) = in(L_{j})x_{n}^{j} for some j and thus in(g) = x_{1}x_{2}...x_{n−1}in(L_{j})x_{n}^{j}. Since in(L_{j}) is divisible by some element of in(ρ(n−1, k −1)), then x_{1}x_{2}..x_{n−1}in(L_{j}) is divisible by some monomial in in(ρ(n, k)) as desired.

If in(g) = in(f) we are done. If they are not equal in(f) cancels with the leading term in the polynomial Q = g − f. Therefore in(Q) = in(f), but for any nonempty S ⊂ {1, .., n − 1} we have in(f_{S}) ≤ in(f) (since we use the lexicographic order). Thus in(Q) = in(f_{T}) for some T ⊂ {1, ..., n − 1} with T non-empty. We observed before that f_{T} ∈ J(p, k), for n > p ≥ k and then in(f) = in(f_{T}) ∈ ⟨in(ρ(p, k))⟩ by the induction hypothesis. Finally we observe that for n > p ≥ k, we have ρ(p, k) ⊂ ρ(n, k). This completes the proof of the theorem.

It is worth commenting on a related family of algebraic varieties which has an interesting relation with stable sets of graphs (see [11]). Let U(n, k) ⊆ K^{n} denote the set of vectors which have k entries equal. U(n, k) is the union of \binom{n}{k} linear subspaces of dimension n − k + 1 given by the equations x_{i_{1}} = x_{i_{2}} = ... = x_{i_{k}} for 1 ≤ i_{1} < ... < i_{k} ≤ n. We write I(n, k) for its vanishing ideal in K[x_{1}, ..., x_{n}]. Let {Z_{1}, ..., Z_{t}} be a finite collection of subsets of {x_{1}, x_{2}, ..., x_{n}}. We define P (Z_{k}) = ∏(x_{i}−x_{j}), where i < j and {x_{i}, x_{j}} run over all distinct unordered pairs of elements of Z_{k} (we let P ({x_{j}}) = 1). We define P ({Z_{1}, ..., Z_{t}}) as ∏ P (Z_{i}). Finally we let μ(n, k) be the set of polynomials P ({Y_{1}, Y_{2}, ..., Y_{j}}) where {Y_{1}, Y_{2}, ..., Y_{j}} is a partition of {x_{1}, x_{2}, ..., x_{n}} into at most k − 1 nonempty parts. The following conjecture is supported by numerous computational experiments.

Conjecture 2.2 The set μ(n, k) is a universal Gröbner basis for the ideal I(n, k).

Li and Li [11] showed that μ(n, k) is a set of generators for the ideal I(n, k). Recently U(n, k) was considered by Björner, Lovász and Yao [8]. They gave lower bounds for the size of linear decision trees for the problem of testing membership in U(n, k). The topology of the complement of the subspace arrangement U(n, k) was studied in [7].

3. Enumeration of vertex colorings

We start this Section with an illustration of Corollary 1.2. For all the computations we used the computer algebra system MACAULAY. The Petersen graph has chromatic number strictly bigger than two. We can write its graph polynomial in terms of the universal Gröbner basis of J(10, 3).

Example 3.1 Let P_{G} be the polynomial associated with the labeling of the Petersen graph that we show in Figure 1.

We have a representation for P_{G} in terms of seven generators P_{G} = ∑_{i=1}^{7} C_{i}P_{H_{i}}. This polynomial identity is a certificate for the fact that the Petersen graph is not bipartite.

Figure 1.

The graphs H_{i} are all isomorphic to a triangle union with seven isolated vertices. The actual values for the polynomials are:

P_{H_{1}} = (f − i)(−i + a)(−f + a)

P_{H_{2}} = (f − j)(−j + a)(−f + a)
P_{H_{3}} = (g − i)(−i + a)(−g + a)
P_{H_{4}} = (−j + g)(−j + a)(−g + a)
P_{H_{5}} = (h − i)(−i + a)(−h + a)
P_{H_{6}} = (h − j)(−j + a)(−h + a)
P_{H_{7}} = (i − j)(−j + a)(−i + a)

C_{1} = −(c−i)(b−i)(b−c)(e−j)(d−j)(d−e)(−c+d)(−e+a)(a−b)(−f +a)(h−i)(−j +g) C_{2} = (c − i)(b − i)(b − c)(e − j)(d − j)(d − e)(−c + d)(−e + a)(a − b)(−f + a)(h − i)(−j + g) C_{3} = (e−j)(d−j)(d−e)(f −j)(−c+d)(b−c)(−f +a)(−e+a)(a−b)(b−i)(h−i)(f +c−i−g) C_{4} = −(e−j)(d−j)(d−e)(f −j)(−c+d)(b−c)(−f +a)(−e+a)(a−b)(b−i)(h−i)(f +c−i−g) C_{5} = (f −j)(−f +g)(c−g)(d−j)(c−d)(d−e)(b−c)(−f +a)(−e+a)(a−b)(b−i)(g+e−j−h) C_{6} = (f−j)(−f+g)(c−g)(d−j)(−c+d)(d−e)(b−c)(−f+a)(−e+a)(a−b)(b−i)(g+e−j−h) C_{7} = −(d − e)(−c + d)(b − c)(−e + a)(a − b)(d − j)(b − i)(−f + a)(−f + g)(cj^{2} − i^{2}j + hj^{2} − gj^{2} + g^{2}j − fg^{2} + ei^{2} − ij^{2} − efi − efg + cef + egj + cfg + fij + hgf − hgj + jfg − hfc − gjc + hce + hef − hfj − hej − hei + cij − cei − cej + hij − fjc + eij).

We remark that in the above example some of the coefficients C_{i} are not polynomials associated with a graph. This is the case for C_{7}. However, L. Lovász proved that, for a graph G, if P_{G} belongs to J(n, k) or I(n, k), then P_{G} has a representation of the form ∑_{i=1}^{N} C_{i}P_{H_{i}} where not only the generators P_{H_{i}} are polynomials coming from graphs but also the coefficients C_{i} (stated without proof in [12]). One can verify such an identity in randomized polynomial time by substituting random values. The representation in terms of the generators for J(n, k) works as a certificate for the fact that the graph G has chromatic number bigger than k − 1. Under the assumption that NP is not equal to randomized co − NP the number of terms N in the above representations must be exponentially long for an infinite family of graphs.

We now apply these ideas to the general question of enumerating distinct colorings. We denote by π(G, k) the number of distinct k-colorings of G. Two k-colorings are distinct if they are distinct as partitions of the set of vertices. Notice that a component of V (n, k) can be identified with a (k − 1)-coloring of a graph on n vertices, where two vertices have the same color if the corresponding entries are equal. We observe that if G is (k − 1)- colorable, P_{G} does not vanish on those irreducible components of V (n, k) that represent good colorings for G. We can detect those components with the operations of ideal quotients and saturations (see chapter four in [3]). The good (k −1)-colorings of G correspond to the irreducible components of the variety associated with the ideal (J(n, k) : P_{G}^{∗}). Here (I : f^{∗}) denotes the ideal of polynomials g ∈ K[x_{1}, ..., x_{n}] with f^{m}g ∈ I for some m > 0. We call (I : f^{∗}) the saturation of I with respect to f.

Lemma 3.2 Let ∩_{i=1}^{m}Q_{i} be a minimal primary decomposition for the ideal I; where Q_{i} is a P_{i}-primary ideal. The saturation ideal (I : f^{∗}) equals ∩_{f∉P_{i}}Q_{i}.

Proof: It is known that (∩_{i=1}^{m}Q_{i} : f^{∗}) = ∩_{i=1}^{m}(Q_{i} : f^{∗}). We observe further that (Q_{i} : f^{∗}) = Q_{i} if f does not belong to P_{i} and (Q_{i} : f^{∗}) = (1) otherwise.

The ideal J = (J(n, k) : P_{G}^{∗}) is a radical ideal and the degree of each irreducible component is one. As a consequence degree deg(J) of the ideal J counts precisely the number of irreducible components. We have the following result:

Proposition 3.3 π(G, k − 1) = deg((J(n, k) : P_{G}^{∗})).

Example 3.4 Consider the 3-colorings of the two-by-four grid graph H. This graph has eight vertices x_{1}, .., x_{8} and ten edges (x_{1}, x_{2}), (x_{2}, x_{3}), (x_{3}, x_{4}), (x_{4}, x_{5}), (x_{5}, x_{6}), (x_{6}, x_{7}), (x_{7}, x_{8}), (x_{1}, x_{8}), (x_{2}, x_{7}), (x_{3}, x_{6}). We want to compute the degree of the ideal (J(8, 4) : P_{H}^{∗}). In order to speed up the computation we observe that the factorization of P_{H} can be used to first compute generators for the saturation ideals (J(8, 4) : (x_{i}−x_{j})^{∗}) for each of the edges of H. We obtain ten such ideals, their intersection is precisely (J(8, 4) : H^{∗}). We use the computer algebra system MACAULAY to compute the saturation ideals and compute a Gröbner basis and degree of the intersection. The degree of the ideal (J(8, 4) : P_{H}^{∗}) is 26. The complete computation in a Sun sparc station 2 took one minute and forty eight seconds.

Other algebraic methods can be used to study chromatic properties of graphs (see [1],[4],[5],[10]). In particular [4] has also suggested the use of Gröbner bases (see chapter three of [1] for a description). Our approach is different because we use a single Gröbner basis for deciding k-colorability of all graphs with n nodes. On the other hand, [4] associates to each graph a specific Gröbner basis when deciding colorability.

4. Gröbner basis interpretation of a result of Alon.

Let f(x) be any polynomial in one variable of degree k with no multiple roots. Consider the polynomial ideal C(f, n, k) in K[x_{1}, ..., x_{n}] generated by the polynomials f(x_{1}), f(x_{2}), ..., f(x_{n}). We notice that an n-tuple (u_{1}, u_{2}, ..., u_{n}) is a zero of this ideal if and only if every entry u_{i} is a root of f. A graph G is not k-colorable if and only if P_{G} belongs to C(f, n, k). It is well known that if the leading monomials of polynomials in a set Γ are pairwise relatively prime, then Γ is a Gröbner basis for the ideal it generates. As a consequence we have:

Proposition 4.1 If f is any one variable polynomial of degree k with no multiple roots, then the set {f(x_{1}), ..., f(x_{n})} is a universal Gröbner basis for the ideal C(f, n, k).

As corollary we have the following criterion for k-colorability:

Corollary 4.2 A graph G with n vertices is k-colorable if and only if the normal form of P_{G} obtained by division modulo {f(x_{1}), ..., f(x_{n})} is non-zero.

A comment is appropriate at this point. The geometric relation between the ideals J(n, k) and C(f, n, k) is very simple. The k^{n} points on the variety V_{f}(n, k) associated with C(f, n, k) are contained in the variety V (n, k), at least one point per irreducible component of V (n, k) (actually with elements such as (u, u, ..., u) where f(u) = 0, that lie in the intersection of several components). If P_{G} vanishes in a generic point belonging to a certain component P_{G} vanishes in the whole component. The variety V (n, k) has S(n, k − 1) irreducible components (the Stirling number of the second kind), so that many points would suffice to test membership into J(n, k) for polynomials P_{G} associated with graphs. The following result is due to N. Alon [2]. We present a “Gröbnerian” proof here:

Proposition 4.3 Assume that the expansion of P_{G} contains a monomial with non-zero coefficient in which every exponent is less than k. Then the graph is k-colorable.

Proof: Suppose m = βx_{1}^{α_{1}}x_{2}^{α_{2}}...x_{n}^{α_{n}} is a monomial of P_{G} with β ≠ 0 and α_{i} < k. We observe that P_{G} is homogeneous of degree equal to the number of edges in the graph. We know that G is not k-colorable if and only if P_{G} belongs to C(f, n, k), where f(x) is a polynomial of degree k with no multiple roots. We claim that P_{G} ∉ C(x^{k} − 1, n, k).

We know that P_{G} ∈ C(x^{k} − 1, n, k) if and only if the normal form of P_{G} with respect to the Gröbner basis {x_{1}^{k} − 1, x_{2}^{k} − 1, x_{3}^{k} − 1, ..., x_{n}^{k} − 1} is zero. This means that the monomial m is cancelled at some point in the process of reduction to the normal form. During the reduction process the degrees of new monomials appearing are strictly smaller than those of the original monomials in P_{G}. Thus m can not cancel with them since it has a higher degree. Since α_{i} ≤ k the monomial m can not cancel with a monomial of the form hx_{i}^{k}, where h is a monomial. Thus m is present in the normal form of P_{G} modulo {x_{1}^{k} − 1, ..., x_{n}^{k} − 1}.

Acknowledgments: I thank my advisor Bernd Sturmfels for many hours of useful conversations and his support and guidance. I also thank Professors A. Björner, L. Lovász and B. Sagan for many useful comments. The comments of the referee improved the presentation and made me aware of relevant references. I am grateful to the National University of México for the financial support I have received during my graduate studies at Cornell.

5. References:

[1] W. Adams and P. Loustaunau: An introduction to Gröbner bases, American Mathematical Society, Providence, Rhode Island, 1994.

[2] N. Alon and M. Tarsi: Colorings and orientations of graphs, Combinatorica 12 (1992), 125-134.

[3] M. Atiyah and I. MacDonald: Introduction to Commutative Algebra, Addison-Wesley, Reading, Massachusetts, 1969.

[4] D. A. Bayer: The Division Algorithm and the Hilbert Scheme, Ph.D Thesis, Harvard University, 1982.

[5] N. Biggs: Algebraic graph theory, Cambridge University press, Cambridge, 1993.

[6] B. Buchberger: Gröbner basis: an algorithmic method in polynomial ideal theory, in: (N.K. Bose ed.) Progress, directions and open problems in multidimensional systems theory, Reidel Publishers, Dordrecht, 1985.

[7] A. Björner and V. Welker: The homology of “k-equal” manifolds and related partition lattices, Advances in Mathematics, to appear.

[8] A. Björner, L. Lovász and A. Yao: Linear decision trees: Volume estimates and topological bounds, in: Proc. 24th Ann. ACM Symp. on Theory of Computing, ACM press, New York, 1992, 170-177.

[9] D. Cox, J. Little and D. O’Shea: Ideals,Varieties and Algorithms, Springer Undergraduate texts in Mathematics, Springer-Verlag, New York, 1992.

[10] S. Eliahou: An algebraic criterion for a graph to be four-colourable, Aportaciones Matemáticas, Soc. Matemática Mexicana, Notas de Investigacion 6 (1992), 3-27.

[11] S.R. Li and W.W. Li: Independence number of graphs and generators of ideals, Combinatorica 1 (1981), 55-61.

[12] L. Lovász: Stable sets and Polynomials, Discrete Mathematics, 124 (1994), 137-153.

[13] L. Lovász: Bounding the independence number of a graph, in (Bachem A, Grötschel M, Korte B. eds.) Bonn Workshop on Combinatorial Optimization, Mathematics Studies 66, Annals of Discrete Mathematics 16, North-Holland, Amsterdam, 1982.

Received August 30, 1994.