# maximum cliques of a subgraph of an interval graph

I have a question: It is known that it is easy to find the maximum cliques of an interval graph. I would like to ask whether the same task is also easy when considering the following subgraph of an interval graph:

Let $$G=(\mathcal{I},E)$$ be an interval graph and let $$k:\mathcal{I}\rightarrow (0,1)$$ be a vertex weight function. Now we delete every edge $$\lbrace i,j \rbrace \in E$$ with $$k_i+k_j \le 1$$ from $$E$$. The remaining edge set is called $$\tilde{E}$$. Moreover, we remove vertices that are not part of an edge anymore, so that we end up with a subgraph $$\tilde{G}=(\tilde{\mathcal{I}},\tilde{E})$$ of $$G$$.

It is also easy to find the maximum cliques of this graph? (I would call it a 'mixture' between an interval graph and a threshold graph.)

Each clique in $$\tilde G$$ contains at most one vertex with weight $$\le \frac12$$. So we can do casework on which of these vertices, if any, we include:
• Find a maximum clique in the subgraph of $$G$$ containing all vertices with weight more than $$\frac12$$. (This clique survives in $$\tilde{G}$$.)
• For each vertex $$i$$ with $$k_i \le \frac12$$, find a maximum clique in the subgraph of $$G$$ containing all vertices adjacent to $$i$$ and with weight more than $$1 - k_i$$. (Such a clique, together with vertex $$i$$ itself, is still a clique in $$\tilde{G}$$.)
• Thanks for your answer. I just have two little questions: (1) Is $\tilde{G}$ really an induced subgraph of $G$? I mean, not all the edges between the nodes $\tilde{I}$ are overtaken from $G$? (2) Am I right that the cliques described in your construction actually form an edge cover of $\tilde{G}$? – Phil Mar 18 at 17:44
• (1) $\tilde{G}$ is definitely not an induced subgraph of $G$! But if we are looking at a set of vertices, each with weight more than $\frac12$, then they induce the same subgraph in $G$ and in $\tilde{G}$, because $\tilde{G}$ keeps all edges between such vertices. – Misha Lavrov Mar 18 at 18:24
• (2) The subgraphs we find include all the edges of $\tilde{G}$ between them - sort of. In the first step, we cover all edges between vertices of weight more than $\frac12$. In the next step, for each vertex $i$ with $k_i \le \frac12$, we cover all edges out of $i$ - sort of, because I defined these subgraphs not to include vertex $i$ itself, but you could modify the definition to include it. The cliques themselves, I don't see why they'd cover all the edges, unless this follows from some property of interval graphs. – Misha Lavrov Mar 18 at 18:26
• Ok, in fact, finally I am looking for an edge cover of $\tilde{G}$ by a preferaby small number of maximum cliques of that graph. (Of course, I had to know first whether or not it is easy to find maximum cliques in $\tilde{G}$.) – Phil Mar 18 at 19:36