Hereditary Properties of Graphs:

Asymptotic Enumeration, Global Structure,

and Colouring

Béla Bollobás

1991 Mathematics Subject Classification: Primary: 05C, 05D; secondary:

51M16, 60E15

1. Introduction. In this paper we shall discuss recent developments concerning hereditary graph properties. In particular, we shall study the growth of the number of graphs with a given hereditary property; the structure of a ‘typical’ graph with the property; and the P-chromatic number of a random graph G_{n,p} for a fixed hereditary property P.

A graph property P is a union of isomorphism classes of finite graphs. To avoid trivialities, we shall always assume that our properties contain infinitely many nonisomorphic graphs, but that for some n do not contain all graphs of order n. Here are some simple examples of graph properties: (i) all triangle-free graphs without 8-cycles, (ii) all graphs of chromatic number at most k, (iii) all graphs containing no induced quadrilaterals, (iv) all regular bipartite graphs, (v) all Hamiltonian graphs.

Rather than considering general properties, we frequently study hereditary properties. A property P is hereditary if it is closed under taking induced subgraphs. In other words, P is hereditary if G ∈ P implies that G − x ∈ P for every vertex x of G.

An important subclass of hereditary properties is the class of monotone properties, those that are closed under taking subgraphs. Thus P is monotone if G ∈ P implies that G − x ∈ P for every vertex x of G and G − e ∈ P for every edge e of G. Note that properties (i) and (ii) are monotone, (iii) is hereditary but not monotone, and properties (iv) and (v) are not hereditary.

The most natural way of measuring the size of a property is to take the number of elements in its finite sections. Given a property P, write P^{n} for the set of graphs in P with vertex set [n] = {1, …, n}. Then (|P^{n}|)_{n=1}^{∞} is, in an obvious sense, a measure of P.

For a monotone property P there is another natural measure: the sequence (e(P^{n}))_{n=1}^{∞}, where e(P^{n}) is the maximal size (number of edges) of a graph in P^{n}. For a general property P, the sequence (e(P^{n}))_{n=1}^{∞} may have little significance, so we have to turn to a natural extension of it. A pregraph is a triple G̃ = (V, Ẽ, Ñ), where V is a finite set, the set of vertices, and Ẽ and Ñ are disjoint subsets of V^{(2)}, the set of unordered pairs of vertices; Ẽ is the set of edges and Ñ is the set of non-edges of G̃. A graph G = (V, E) extends G̃ if Ẽ ⊂ E ⊂ V^{(2)} \ Ñ. The size e ˜ (G) of a pregraph is |V^{(2)} \ (Ẽ ∪ Ñ)|: the number of choices we have when extending G̃ to a graph. We say that a pregraph G̃ belongs to P^{n} if every graph extending G̃ belongs to P^{n}. Then another natural measure of the size of a property P is the sequence (e_{n}(P))_{n=1}^{∞}, where e_{n}(P) is the maximal size of a pregraph in P^{n}.

It is natural to identify a graph G = (V, E) with the pregraph G̃ = (V, ∅, V^{(2)}\ E); with this identification we find that e(G) = e(G̃). Hence, for a monotone property P, the two definitions give the same value: in other words, e(P^{n}) = e_{n}(P).

Scheinerman and Zito [28] were the first to study the rate of growth of |P^{n}| for a hereditary property. They discovered that, crudely, |P^{n}| behaves in one of the following five ways: (i) for n large enough, |P^{n}| = 1 or 2, (ii) it grows polynomially: for some positive integer k, a_{1}n^{k} ≤ |P^{n}| ≤ a_{2}n^{k} for some a_{1}, a_{2} > 0, (iii) it grows exponentially: aa_{1}^{n} ≤ |P^{n}| ≤ a_{2}^{n} for some a > 0 and 1 < a_{1} ≤ a_{2}, (iv) it grows factorially: an^{a_{1}n} ≤ |P^{n}| ≤ n^{a_{2}n} for some a > 0 and 0 < a_{1} ≤ a_{2}, (v) it grows superfactorially: |P^{n}| > n^{an} for every a > 0 and n large enough.

Here we are interested in properties whose rate of growth is not far from maximal. To measure the rate of growth of such a property P, we replace the sequence (|P^{n}|)_{n=1}^{∞} by the sequence (c_{n})_{n=1}^{∞}, where |P^{n}| = 2^{c_{n}\binom{n}{2}}. Since 1 ≤ |P^{n}| ≤ 2^{\binom{n}{2}}, we have 0 ≤ c_{n} ≤ 1.

We call c_{n} the logarithmic density of P^{n}, and c = lim_{n→∞} c_{n} the asymptotic logarithmic density of P provided the limit exists.

Similarly, the (normalized) size of P^{n} is d_{n}, 0 ≤ d_{n} ≤ 1, defined by e_{n}(P) = d_{n}\binom{n}{2}.

The asymptotic size of P is d = lim_{n→∞} d_{n}, provided this limit exists. Since every pregraph G̃ extends to 2^{e(G̃)} graphs, we have c_{n} ≥ d_{n} for every property. Hence if P is a property with asymptotic logarithmic density c and asymptotic size d, then c ≥ d. We shall see later that every hereditary property has an asymptotic logarithmic density c and an asymptotic size d and, in fact, they are equal.

2. Monotone properties. One of the main aims of classical extremal graph theory is the study of the sequence (e_{n}(P))_{n=1}^{∞} for various monotone graph properties. Frequently, a monotone property is given by a family F of forbidden subgraphs. For a family F = {F_{1}, F_{2}, …} of finite graphs, let Mon(F) be the collection of all graphs containing no F_{i} as a subgraph. Clearly every monotone property is of the form Mon(F) for some family F of forbidden subgraphs, but one is especially interested in monotone families defined by small families of forbidden subgraphs. If there is only one forbidden subgraph F then we have a principal monotone property and we write Mon(F) instead of Mon({F }).

It has been known for over fifty years that every monotone graph property has an asymptotic size. In particular, a weak form of Turán’s theorem [31] states that d(Mon(K_{r+1})) = 1 − \frac{1}{r} for every r ≥ 1. The fundamental theorem of Erdős and Stone [15] extends this result to d(Mon(K_{r+1}(t))) = 1 − \frac{1}{r} for all r, t ≥ 1. Here, as usual, K_{n} denotes a complete graph of order n and K_{r}(t) denotes the complete r-partite graph in which each part has t vertices. An equivalent form of the Erdős-Stone theorem is that if F is any family of forbidden subgraphs then d(Mon(F)) = 1 − \frac{1}{r}, where r = min\{χ(F) − 1 : F ∈ F\} and χ(F) is the chromatic number of F.

Rather more effort is needed to prove that every monotone property has an asymptotic density. Using the method of Kleitman and Rothschild [18], Erdős, Kleitman and Rothschild [12] proved that c(Mon(K_{r+1})) = 1 − \frac{1}{r}. This result was extended by Erdős, Frankl and Rödl [11], who proved that c(Mon(F)) = 1 − \frac{1}{r} for every graph F, where r = χ(F) − 1. The proof of this result implies that c(Mon(F)) = 1 − \frac{1}{r} for every family F, where r is, as before, one smaller than the minimal chromatic number of a graph in F. In particular, c(P) = d(P) for every monotone family.

The structure of K_{r+1}-free graphs was investigated in great detail by Kolaitis, Prőmel and Rothschild [19]. Among other results, they proved that Mon(K_{r+1}) is well approximated by the smaller property N_{r} of graphs of chromatic number at most r: not only do we have the crude result that c(Mon(K_{r+1})) = c(N_{r}), but also

|Mon(K_{r+1})^{n}|/|N_{r}^{n}| = 1 + O(n^{−k})

for all k > 0. Furthermore, a first-order labelled 0 − 1 law holds for the class of K_{r+1}-free graphs.

Before leaving monotone properties, let us note that the following somewhat surprising fact is an immediate consequence of the description of c(P) = d(P) for a monotone property. If P_{1} and P_{2} are monotone properties, and P = P_{1} ∩ P_{2}, then

c(P) = min{c(P_{1}), c(P_{2})}.  (1)

Thus the intersection of two monotone properties is about as large as the smaller of the two properties!

3. Volumes of projections and asymptotic enumeration. The existence of the asymptotic logarithmic density of a hereditary property is closely related to a family of inequalities involving volumes of projections of bodies. Our next aim is to describe this relationship.

A body in R^{n} is a compact convex subset of R^{n} that is the closure of its interior. Let v_{1}, …, v_{n} be the standard basis of R^{n} = lin{v_{1}, …, v_{n}}. For a subset A of [n], write K_{A} for the orthogonal projection of a body K onto lin{v_{j} : j ∈ A}, and |K_{A}| for the |A|-dimensional volume of K_{A}. In particular, |K| = |K_{[n]}| is the volume of K. With β(K) = (|K_{A}| : A ⊂ [n]) = (|K_{A}|)_{A⊂[n]} ∈ R^{P(n)} = R^{2^{n}}, the map K → β(K) can be considered to be a measure of the size of the boundary of K.

We are interested in the best possible isoperimetric inequalities involving the boundary vector β(K) and the volume |K|. In other words, we would like to know for which vectors (x_{A}) ∈ R^{2^{n}} with x_{[n]} = 1 is there a body K ⊂ R^{n} of volume 1 such that |K_{A}| ≤ x_{A} for all A ⊂ [n]. The following box theorem we proved with Thomason [6] gives a surprisingly simple answer to this question. A box B in R^{n} is a body of the form B = ∏_{j=1}^{n} I_{j}, where each I_{j} is an interval.

Theorem 1. For every body K ⊂ R^{n}, there is a box B ⊂ R^{n} such that |B| = |K| and |B_{A}| ≤ |K_{A}| for every A ⊂ [n].

An immediate consequence of the box theorem is the uniform cover inequality below, extending the Loomis-Whitney inequality [20]. A sequence (A_{i})_{i=1}^{m} of subsets of [n] is a k-uniform cover of [n] if every element of [n] belongs to precisely k of the sets A_{1}, …, A_{m}. Now, if (A_{i})_{i=1}^{m} is a k-uniform cover of [n], and K is a body in R^{n} then Theorem 1 implies that

|K|^{k} ≤ ∏_{i=1}^{m} |K_{A_{i}}|.  (2)

In fact, in [6] the box theorem is deduced from the uniform cover inequality (1) by a simple compactness argument. Since the original proof, several other deductions have been suggested: Ball noted that separation theorems, and Kahn and Meshulam pointed out that properties of submodular functions, can be used to deduce the box theorem from inequality (2).

The box theorem easily implies that, as first proved by Alekseev [1], every hereditary property of graphs has an asymptotic logarithmic density.

Theorem 2.Let P be a hereditary property of graphs. Then 1 = c_{1}(P) ≥ c_{2}(P) ≥ ⋯; in particular, the asymptotic logarithmic density c(P) = lim_{n→∞} c_{n}(P) exists.

It is easily seen that the arguments above apply to hereditary properties of r-uniform hypergraphs as well, mutatis mutandis.

4. Asymptotic enumeration and global structure. Given a family F = {F_{1}, F_{2}, …}, of finite graphs, let Her(F) be the collection of all graphs that contain no F_{i} as an induced subgraph. Clearly, every hereditary property is of the form Her(F) for some family F of forbidden subgraphs. Theorem 2 tells us that every hereditary property P = Her(F) has an asymptotic logarithmic density c(P), but gives no indication as to how one could determine c(P) from F. In fact, Prömel and Steger [22], [23], [24], [25] gave such a description for a principal hereditary property, i.e., for one with a single forbidden induced subgraph. They also gave approximations of principal hereditary properties by rather simple (non-principal) hereditary properties. With Thomason [7] we extended these results to general hereditary properties.

Before we can describe these results, we have to introduce some definitions. An (r, s)-colouring of a graph G = (V, E) is a partition of the vertex set into r classes such that the first s classes induce complete graphs, and the remaining r −s classes induce empty subgraphs. (Needless to say, empty classes are allowed.) Thus an (r, 0)-colouring of a graph is precisely a standard r-colouring. We write P_{r,s} for the collection of all (r, s)-colourable graphs; clearly, P_{r,s} is a hereditary property for all 0 ≤ s ≤ r, r ≥ 1. For example, P_{1,1} is the collection of all complete graphs, and P_{1,0} is the collection of all empty graphs. The colouring number r(P) of a property P is

r(P) = max{r : P_{r,s} ⊂ P for some s}.

Note that if P = Her(F) then

r(P) = max{r : for some s ≤ r, no F ∈ F is (r, s)-colourable}.

If P = Mon(F) then r(P) is exactly as before:

r(P) = min{χ(F) − 1 : F ∈ F} = max{r : no F ∈ F is (r, 0)-colourable}.

The colouring number gives us a lower bound for c_{n} and d_{n}. Indeed, let 0 ≤ s ≤ r be such that r = r(P) and P_{r,s} ⊂ P, and let G̃ = ([n], Ẽ, Ñ) be the pregraph obtained as follows. Partition [n] into r classes as equal as possible in size, [n] = V_{1} ∪ … ∪ V_{r}, say, and let Ẽ consist of all edges within a class V_{i} for 0 ≤ i ≤ s. Since P_{r,s} ⊂ P, every extension of G̃ belongs to P. Consequently,

c_{n}(P) ≥ d_{n}(P) ≥ e(G̃)/\binom{n}{2} ≥ 1 − \frac{1}{r}.

As shown in [7], c(P) and d(P) exist for every hereditary property, and these inequalities are essentially best possible.

Theorem 3. If P is any hereditary property then

c(P) = d(P) = 1 − \frac{1}{r(P)},

where r(P) is the colouring number of P.

The proof of this theorem is based on the three pillars of extremal graph theory: the theorems of Ramsey [26], Erdős and Stone [15], and Szemerédi [30]. One needs only the very simple case of Ramsey’s theorem that the diagonal graph Ramsey function is finite: R(k) < ∞ for every k. On the other hand, one needs a slight extension of the Erdős-Stone theorem: for all r, t ≥ 1 and ϵ > 0 there are δ > 0 and n_{0} ∈ N such that if F and G are graphs with V (F) = V (G) = [n], n ≥ n_{0}, e(F) ≤ δn^{2} and

e(G) ≥ (1 − \frac{1}{r} + ϵ)\binom{n}{2},

then G contains an F -avoiding K_{r+1}(t). Here we say that a graph H avoids F if no edge of F joins two vertices of H.

The most important ingredient of the proof of Theorem 3 is Szemerédi’s uniformity lemma [30]. Given a graph G = (V, E), and subsets A, B, ⊂ V, the density d(A, B) is defined as

d(A, B) = \frac{e(A, B)}{|A||B|},

where e(A, B) is the number of A-B edges. A pair (A, B) is (ϵ, δ)-uniform if

|d(A′, B′) − d(A, B)| ≤ ϵ

whenever A′ ⊂ A, B′ ⊂ B, |A′| ≥ δ|A| and |B′| ≥ δ|B|.

Szemerédi’s uniformity lemma states that for all ϵ, δ, η > 0 there is an M = M(ϵ, δ, η) such that the vertex set of every graph G can be partitioned into at most M sets U_{1}, …, U_{m} of sizes differing by at most 1, such that at least (1 − η)m^{2} of the (ordered) pairs (U_{i}, U_{j}) are (ϵ, δ)-uniform.

The fewer sets U_{1}, U_{2}, … we can take the more powerful the result is; unfortunately when ϵ = δ = η, all we know about M(ϵ, ϵ, ϵ) is that it is at most a tower of 2s of height proportional to ϵ^{−5}. As the proof of this bound seemed rather ‘wasteful’, for many years there had been some hope that this enormous bound could be reduced greatly. It was a great surprise when recently Gowers [17] proved the difficult result that K(ϵ, δ, η) can not be less than of tower type in 1/δ, even when ϵ and η are kept large.

Szemerédi’s uniformity lemma implies that every graph satisfying certain global conditions contains appropriate induced subgraphs; this is precisely how the lemma was used in the proof of Theorem 3.

The descriptions of the asymptotic logarithmic density and asymptotic size of a hereditary property provided by Theorem 3 imply that hereditary properties are much more complex than monotone ones. In particular, the simple relationship (1) fails for hereditary properties. For example, if P_{1} = Her(K_{4}), P_{2} = Her(C_{7}) and P = P_{1} ∩ P_{2} = Her{K_{4}, C_{7}}, then r(P_{1}) = r(P_{2}) = 3 but r(P) = 2: the intersection of two hereditary properties can be much smaller than either of them.

In fact, the intersection of two large hereditary properties need not even be a property in our sense: it may contain only finitely many non-isomorphic graphs. For example, if r ≥ 1 then each of P_{r,0} and P_{r,r} has colouring number r, so that c(P_{r,0}) = c(P_{r,r}) = 1 − \frac{1}{r}, but P_{r,0} ∩ P_{r,r} consists of graphs G with χ(G) ≤ r and χ(Ḡ) ≤ r. In particular, |G| ≤ r^{2} for every G ∈ P_{r,0} ∩ P_{r,r}, so P_{r,0} ∩ P_{r,r} indeed consists only of finitely many non-isomorphic graphs.

5. Colouring random graphs G_{n,1/2} with hereditary properties. The random graph G_{n,p} is a graph with vertex set [n], whose edges are selected independently, with probability p. The probability space of these graphs is G(n, p). In particular, G(n, 1/2) is the space of all 2^{\binom{n}{2}} graphs on [n] with the uniform distribution.

One of the main questions left open by Erdős and Rényi when, almost forty years ago, they founded the theory of random graphs ([13], [14]; see also [5]) was the behaviour of the chromatic number of a random graph. Over 25 years later, first Shamir and Spencer [29] proved that the chromatic number of G_{n,p} is highly concentrated, and then it was shown [3] that if 0 < p < 1 is fixed and q = 1 − p then

χ(G_{n,p}) = (1 + o(1))\frac{n}{2 log_{1/q} n}  (3)

for almost every G_{n,p}. Substantial extensions of this result were proved by Łuczak [21], Frieze and Łuczak [16], and Alon and Krivelevich [2]. All these results use various martingale inequalities (see [4]).

For a property P, a P-colouring of a graph G = (V, E) is a partition V = V_{1} ∪ …∪V_{k} of the vertex set such that every class V_{i} induces a P-graph: G[V_{i}] ∈ P, i = 1, …, k. The P-chromatic number χ_{P}(G) of a graph G is the minimal number of classes in a P-colouring of G. Thus χ_{P_{1,0}}(G) = χ(G) and χ_{P_{1,1}}(G) = χ(\overline{G}). Scheinerman [27] was the first to study the P-chromatic number of random graphs. He noted that if P is a hereditary property then either P_{1,0} ⊂ P or P_{1,1} ⊂ P so χ_{P}(G) ≤ max\{χ(G), χ(\overline{G})\}. From this it follows that χ_{P}(G_{n,p}) = O(n log n) for every fixed 0 < p < 1 and hereditary property P, and it is easily seen that, in fact, χ_{P}(G_{n,p}) = Θ(n log n).

With Thomason [8] we proved an analogue of (3) for a general hereditary property, but only in the case p = \frac{1}{2}.

Theorem 4. Let P be a non-trivial hereditary property of graphs, with colouring number r = r(P). Then

χ_{P}(G_{n,1/2}) = (\frac{1}{2r} + o(1))\frac{n}{log_{2} n}

for almost every G_{n,1/2}.

In fact, this result follows rather easily from (3) and from the facts that c(P) = 1− \frac{1}{r} and that P_{r,s} ⊂ P for some s, 0 ≤ s ≤ r. More precisely, c(P) = 1− \frac{1}{r} implies that χ_{P}(G_{n,1/2}) is unlikely to be much smaller than n/(2r log_{2} n), and P_{r,s} ⊂ P implies that χ_{P}(G_{n,1/2}) is unlikely to be much larger than n/(2r log_{2} n).

6. Colouring random graphs G_{n,p} with hereditary properties. The accepted wisdom in the theory of random graphs is that whatever can be proved for the space G(n, p) with p = 1/2 can be proved for G(n, p) with any fixed p, 0 < p < 1. This conventional wisdom is contradicted by the problem of determining χ_{P}(G_{n,p})! As we saw in Theorem 4, it is easy to determine χ_{P}(G_{n,p}) in the uniform case p = 1/2. However, for p ≠ 1/2 not only does the proof collapse, but we are faced with a genuinely more complicated phenomenon, so that much more effort is needed to overcome the difficulties.

A lower bound for χ_{P}(G_{n,p}) is easily obtained from the following result, which is a consequence of the box theorem.

Theorem 5. Let P be a hereditary graph property, let 0 < p < 1 and let the constants e_{k,p}(P) be defined by P(G_{k,p} ∈ P) = 2^{−e_{k,p}(P)\binom{k}{2}}. Then e_{k,p}(P) increases with k. In particular, e_{k,p}(P) tends to a limit e_{p}(P) as k → ∞. Furthermore, e_{p}(P) > 0 if P is non-trivial, i.e., if not every graph has P.

Theorem 5 implies that, for ϵ > 0, the expected number of induced subgraphs of order k in a random graph G_{n,p} having property P is o(1) for k ≥ (2/e_{p} + ϵ) log_{2} n, and tends to infinity for k ≤ (2/e_{p} − ϵ) log_{2} n. Consequently,

χ_{P}(G_{n,p}) ≥ (e_{p} + o(1))n/(2 log_{2} n)  (4)

almost surely.

It was conjectured in [8] that (4) is in fact an equality, as claimed by Theorem 4 for p = 1/2. Now, the proof of Theorem 4 is based on the fact that for p = 1/2 the constant e_{p}(P) has a simple interpretation in terms of the values (r, s) for which P_{r,s} ⊂ P. However, for p ≠ 1/2 this is no longer true: e_{p}(P) cannot be characterized solely in terms of these values (r, s). For example, let P′ = P_{2,0} be the property of being bipartite, and let P′′ be the property of being 3-colourable, with two of the colour classes spanning complete bipartite graphs. Then P′ and P′′ contain P_{1,0} and P_{2,0}, and no other P_{r,s}. Nevertheless, e_{p}(P′) ≠ e_{p}(P′′) for p > 1/2.

In spite of these difficulties, with Thomason [9] we proved the conjecture above.

Theorem 6. Let P be a hereditary graph property and let 0 < p < 1. Let e_{p} = e_{p}(P) be the constant defined in Theorem 5. Then

χ_{P}(G_{n,p}) = (e_{p} + o(1))n/(2 log_{2} n)

almost surely.

The proof of Theorem 6 makes use of Szemerédi’s uniformity lemma, martingale inequalities and, above all, a careful study of the structure of a general hereditary property. The product ∏_{γ∈Γ} P_{γ} of hereditary properties P_{γ}, γ ∈ Γ, is the class of graphs G with vertex sets ⋃_{γ∈Γ} V_{γ} such that G[V_{γ}] ∈ P_{γ} for every γ ∈ Γ. A hereditary property is irreducible if it is not the product of two other hereditary properties. It is easily shown that every hereditary property is the product of a finite collection of irreducible hereditary properties. Also, if P = ∏_{γ∈Γ} P_{γ} then

e_{p}(P)^{−1} = ∑_{γ∈Γ} e_{p}(P_{γ})^{−1}.

Next, one can show that if Theorem 6 holds for each of the properties P_{1}, …, P_{k}, then it holds for ∏_{i=1}^{k} P_{i} as well. Consequently, it suffices to prove Theorem 6 for irreducible properties.

In fact, the heart of the proof is the assertion that Theorem 6 holds for every ‘typed’ property P = P(τ). A type is a labelled graph, each of whose vertices and edges is coloured black or white. Given a type τ, the property P(τ) consists of those graphs G for which V (G) has a partition ⋃_{t∈V (τ)} V_{t} such that G[V_{t}] is complete or empty according as t is black or white, and moreover, if the edge tu is in τ then G[V_{t}, V_{u}] is a complete or empty bipartite graph according as the edge tu is black or white. The proof of the fact that Theorem 6 holds for typed properties P(τ) is based on a careful analysis of the maximal number of induced edge-disjoint subgraphs of a given order having property P – after much work enough can be deduced so that martingale inequalities can be applied.

7. Open problems. Numerous open problems remain. Concerning graphs, all the discussion above is about rather ‘rich’ properties P, namely those with c(P) > 0. The case c(P) = 0 is not understood nearly as well.

Although we know that c(P) = d(P) for every hereditary property, this is far from being the entire story. We always have

|P^{n}| = 2^{c_{n}\binom{n}{2}} ≥ 2^{e_{n}(P)} = 2^{d_{n}\binom{n}{2}},

but it would be good to decide whether c_{n} = (1 + o(1))d_{n} holds as well.

More importantly, we know very little about hypergraphs. The quantities c_{n}(P) and d_{n}(P) are easily defined for r-graphs, and c_{n}(P) ≥ d_{n}(P) for every n. Also, the box theorem implies that c_{n}(P) → c(P), and one can show that d_{n}(P) → d(P), but we do not know whether we always have c(P) = d(P). Nothing of importance is know about the P-chromatic number of r-graphs: we do not even know the asymptotic P-chromatic number of random r-graphs G_{n,p}^{(r)} for p = 1/2.

References

[1] V.E. Alekseev, On the entropy values of hereditary classes of graphs, Discrete Math. Appl. 3 (1993), 191–199.

[2] N. Alon and M. Krivelevich, The concentration of the chromatic number of random graphs, Combinatorica 17 (1997), 303–313.

[3] B. Bollobás, The chromatic number of random graphs, Combinatorica 8 (1988), 49–55.

[4] B. Bollobás, Martingales, isoperimetric inequalities and random graphs, in “Combinatorics (Eger, 1987)” (A. Hajnal, L. Lovász and V.T. Sós, eds.), Colloq. Math. Soc. János Bolyai 52, North-Holland, Amsterdam (1988), 113–139.

[5] B. Bollobás, Random Graphs, Academic Press, London, 1985, xvi+447pp.

[6] B. Bollobás and A. Thomason, Projections of bodies and hereditary properties of hypergraphs, J. London Math. Soc. 27 (1995), 417–424.

[7] B. Bollobás and A. Thomason, Hereditary and monotone properties of graphs, in “The Mathematics of Paul Erdős II” (R.L. Graham and J. Nešetřil, eds.) Algorithms and Combinatorics, Vol. 14, Springer-Verlag (1997), 70–78.

[8] B. Bollobás and A. Thomason, Generalized chromatic numbers of random graphs, Random Structures and Algorithms 6 (1995), 353–356.

[9] B. Bollobás and A. Thomason, Colouring random graphs by hereditary properties, to appear.

[10] B. Bollobás and P. Erdős, On the structure of edge graphs, Bull. London Math. Soc. 5 (1973), 317–321.

[11] P. Erdős, P. Frankl and V. Rödl, The asymptotic enumeration of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent, Graphs and Combinatorics 2 (1986), 113–121.

[12] P. Erdős, D.J. Kleitman and B.L. Rothschild, Asymptotic enumeration of K_{n}-free graphs, in International Coll. Comb., Atti dei Convegni Lincei (Rome) 17 (1976), 3–17.

[13] P. Erdős and A. Rényi, On random graphs I, Publ. Math. Debrecen 6 (1959), 290–297.

[14] P. Erdős and A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1961), 17–61.

[15] P. Erdős and A.H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.

[16] A.M. Frieze and T. Łuczak, On the independence and chromatic numbers of random regular graphs, J. Combinat. Theory (B) 54 (1992), 123–132.

[17] W.T. Gowers, Lower bounds of tower type for Szemerédi’s uniformity lemma, Geom. Funct. Anal. 7 (1997), 322-332.

[18] D.J. Kleitman and B.L. Rothschild, Asymptotic enumeration of partial orders on a finite set, Trans. Amer. Math. Soc. 205 (1975), 205–220.

[19] Ph.G. Kolaitis, H.J. Prömel and B.L. Rothschild, K_{l+1}-free graphs: asymptotic structure and a 0–1 law, Trans. Amer. Math. Soc. 303 (1987), 637–671.

[20] L.H. Loomis and H. Whitney, An inequality related to the isoperimetric inequality, Bull. Amer. Math. Soc., 55 (1949), 961–962.

[21] T. Łuczak, The chromatic number of random graphs, Combinatorica 11 (1991), 45–54.

[22] H.J. Prömel and A. Steger, Excluding induced subgraphs: quadrilaterals, Random Structures and Algorithms 2 (1991), 55–71.

[23] H.J. Prömel and A. Steger, Excluding induced subgraphs II: extremal graphs, Discrete Applied Mathematics 44 (1993), 283–294.

[24] H.J. Prömel and A. Steger, Excluding induced subgraphs III: a general asymptotic, Random Structures and Algorithms 3 (1992), 19–31.

[25] H.J. Prömel and A. Steger, The asymptotic structure of H-free graphs, in Graph Structure Theory (N. Robertson and P. Seymour, eds), Contemporary Mathematics 147, Amer. Math. Soc., Providence, 1993, pp. 167-178.

[26] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30(2) (1929), 264–286.

[27] E.R. Scheinerman, Generalized chromatic numbers of random graphs, SIAM J. Discrete Math. 5 (1992), 74–80

[28] E.R. Scheinerman and J. Zito, On the size of hereditary classes of graphs, J. Combinat. Theory (B) 61 (1994), 16–39.

[29] E. Shamir and J. Spencer, Sharp concentration of the chromatic number on random graphs G_{n,p}, Combinatorica 7 (1987), 121–129.

[30] E. Szemerédi, Regular partitions of graphs, in Proc. Colloque Inter. CNRS (J.-C. Bermond, J.-C. Fournier, M. las Vergnas, D. Sotteau, eds), 1978.

[31] P. Turán, On an extremal problem in graph theory (in Hungarian), Mat. Fiz. Lapok 48 (1941), 436–452.

Béla Bollobás

Dept. of Mathematics, Univ. of Memphis, USA and Trinity College, Univ. of Cambridge, England