Hereditary graph property

A hereditary graph property is closed under taking induced subgraphs. It can be described by forbidden induced graphs. Unlike subgraph closure, this condition allows edges to be essential to membership. Its colouring number of a hereditary graph property governs its quadratic enumeration rate.

This parameter measures the largest completely unrestricted clique-independent partition class contained in the property. It is zero for bounded-order hereditary classes and infinite for all graphs. For proper unbounded classes it is a positive integer; it differs from the degeneracy-based colouring number of an individual graph.

For a proper hereditary graph property with unbounded orders, the colouring number determines the leading labelled speed. The lower bound comes from one contained clique-independent partition class. For the upper bound, forbid one induced graph from each next-size partition type and use the induced regularity template lemma. Its intermediate-pair graph is clique-free, and sparse or almost-complete pairs have negligible entropy. Bounded-order properties have colouring number zero and are outside this formula.

Graphs in $\mathcal{C}(a,b)$ admit a partition into $a$ total classes, of which $b$ are designated cliques and $a-b$ are designated independent sets. Cross edges are arbitrary and empty classes are allowed. Balanced cross-edge choices give quadratic labelled speed coefficient $1-1/a$. Comparing this count with every $(a+1)$-class type shows that the hereditary colouring number of this class is exactly $a$.