Colouring number of a hereditary graph property ($r(\mathcal{P})=\max \{a:\mathcal{C}(a,b)\subseteq \mathcal{P}\text{ for some }b\}$)

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.