1
$\begingroup$

I faced the following claim on wikiepdia about interval graphs (https://en.wikipedia.org/wiki/Interval_graph):

The pathwidth of an interval graph is one less than the size of its maximum clique.

I have thought a while about it, but don't come up with any argument/proof why the pathwidth is bounded by the size of the maximum clique-1. Is there a "simple" proof why that is so? Or is it just the fact, that any clique must be contained in some bag of a tree/path decomposition?

$\endgroup$

1 Answer 1

0
$\begingroup$

Or is it just the fact, that any clique must be contained in some bag of a tree/path decomposition?

To prove the claim one should prove, both, that the pathwidth is at most the maximum clique size - 1 (e.g., by construction), and that there does not exists a clique not contained in a bag as you observed. For interval graphs, a construction proving the first part is pretty much given by their definition.

The second, and perhaps a less obvious part, can be proved, for example, by induction on the max. clique size k, and can be also found in many text books, for example, as Lemma 12.3.5 of the 3rd edition of Diestel's book.

A proof of the lemma for path decomposition goes by induction goes as follows.

Base Step: The claim holds for cliques of size 1 and 2, which are just vertices and edges, respectively, by the definition. That concludes the base case.

Inductive step: Take a clique K of size k>2, and consider two cliques Ku and Kv of size k-1 obtained by removing vertices u and v, respectively, from K. By the induction hypothesis both Ku and Kv as well as the edge uv are contained in their bags. Now, there are three cases to consider.

If any of these bags are the same then we are done, since then there exists a bag that contains the whole K.

If the bag B containing uv is between the bags containing Ku and Kv, by the definition of the path decomposition, B also contains all the vertices in the intersection of Ku and Kv. Therefore B contains the whole K.

If the bag B containing uv is NOT between the bags containing Ku and Kv. Then either the bag containing Ku is between B and the bag containing Kv, or the bag containing Kv is between B and the bag containing Ku. In the former, by the definition of the path decomposition, the bag containing Ku also contains v and therefore the whole K. In the latter, by the definition of the path decomposition, the bag containing Kv also contains u and therefore the whole K.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.