The pathwidth of a graph G is the minimum, over all interval supergraphs H of G, of the size of the largest clique in H (minus one).

The tree-depth of a graph G is the minimum, over all trivially perfect supergraphs H of G, of the size of the largest clique in H.

The vertex cover number of a graph G is within one of the minimum, over all threshold supergraphs H of G, of the size of the largest clique in H. (One could use split graphs instead but it changes the clique size by at most one.)

There is a strict chain of inclusions of graph families: threshold ⊂ trivially perfect ⊂ interval ⊂ chordal. This implies a corresponding chain of near-inequalities among the corresponding graph parameters, but some of them are not exact because of the off-by-one differences between the graph parameters and clique sizes.

Are there more like this that I'm missing?

## Error

Your reply will be screened

Your IP address will be recorded