Membership is preserved under deleting vertices and edges. This is the decreasing meaning of monotonicity in extremal graph enumeration; it differs from an increasing monotone graph property used for random-graph thresholds. For a proper unbounded class, its least excluded chromatic number determines the leading quadratic logarithm of its labelled speed.
Here is the least chromatic number of an excluded graph, for a proper unbounded subgraph-closed property. All subgraphs of a balanced Turan graph give the lower bound. For the upper bound, a regularity reduced graph is clique-free, so its dense pairs have the Turan theorem edge bound; sparse pairs contribute only small binary entropy and the bounded partition description costs only a linear number of bits.
Articles by others on the same topic
There are currently no matching articles.