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

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?


Comments:

None:
2012-11-16T03:08:51Z

The bandwidth of a graph \( G \) is the minimum, over all proper interval supergraphs \( H \) of \( G, \) of the size of the largest clique in \( H \) (minus one). Kaplan and Shamir (1996) http://dx.doi.org/10.1137/S0097539793258143

11011110:
2012-11-16T05:08:50Z

Another good example — thanks!

None:
2012-11-16T17:35:34Z

Perhaps chromatic number and perfect supergraphs?

11011110:
2012-11-16T18:13:56Z

Another good one. I don't know of a lot of graph algorithms parameterized by chromatic number, and I don't know of a reference for this equivalence, but I think this does work, and adds to the chain of inequalities.

Here's a quick proof sketch. In one direction, it's obvious that chromatic number ≤ perfect clique number. In the other direction, if you have a k-coloring, you can extend it to a complete k-partite graph, which has the same chromatic number and is necessarily perfect (either show this directly from the fact that every induced subgraph is also complete multipartite, or observe that perfect graphs are closed under complement and the complement of a complete k-partite graph is just a disjoint union of cliques).

tbiedl:
2012-12-14T12:07:08Z

Since vertex cover number corresponds to split graphs (more or less), then I wonder what kind of graph class the twin cover number corresponds to?

11011110:
2012-12-14T13:38:57Z

I don't know about that one. The correct reference is Ganien's IPEC 2012 paper "Twin-Cover: Beyond Vertex Cover in Parameterized Algorithmics", right?