0xDE (11011110 ) wrote,

Graph parameters and cliques in supergraphs

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?
Tags: graph theory
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 7 comments