Sign up ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

It's formulated by extending threshold graphs. Given a threshold graph $(C,I)$ where $C$ is the clique and $I$ is the independent set, my extension is as follows: Each vertex $v\in I$ can be replaced by a new clique $K_v$ such that the vertices of $K_v$ have the same neighbors of $v$.

I guess this should have been studied, but it is hard to search such thing in

share|cite|improve this question
It seems to be intersection graph of nested intervals (, but I need to check. –  Yixin Cao Dec 4 '12 at 14:31

1 Answer 1

up vote 15 down vote accepted

I believe that these are exactly the ($C_4$, $P_4$, $2P_3$)-free graphs — that is, the graphs whose induced subgraphs do not include 4-cycles, 4-vertex paths, or the graphs formed from the disjoint union of two 3-vertex paths. This class seems to lie between the threshold graphs themselves, which may be characterized as the ($C_4$, $P_4$, $2K_2$)-free graphs, and the trivially perfect graphs (intersections of nested intervals), which may be characterized as the ($C_4$, $P_4$)-free graphs. I don't think it has a name; at least, it doesn't seem to be listed at

To see that this is the correct characterization, consider the representation of trivially perfect graphs as the transitive closures of rooted forests. A forest gives rise to a (connected) threshold graph if and only if it has a directed path that contains all non-leaf nodes: adding a new isolated vertex corresponds, in the forest, to adding a new single-node tree, which doesn't change this property, and adding a new vertex connected to all of the others corresponds to adding a new root connected to all the previous tree roots, which again doesn't change this property (the new root can be part of the path).

Now your clique-replacement operation corresponds, in the tree view of a trivially perfect graph, to subdividing tree edges into paths (or replacing a one-vertex tree by a path). The forests that you can get from this operation are the ones in which there is a single directed path that contains all nodes with two or more children. A forest has such a path if and only if it does not have two unrelated forks (nodes with two or more children, neither of which can reach each other). And the subgraph you get in your trivially perfect graph when there are two forks is exactly $2P_3$.

The graphs whose complements are in the class you ask about — that is, the ($2K_2$,$P_4$,co-$2P_3$)-free graphs — were studied by Gurski, who showed that they are the same as the graphs of linear clique-width at most two. See theorem 10 of Gurski, Frank, "Characterizations for co-graphs defined by restricted NLC-width or clique-width operations", Discrete Math. 306 (2006), no. 2, 271–277.

share|cite|improve this answer
Thanks for your detailed explanation. Do we really need $2 P_3$ here? Should it be $(C_4,P_4)$-free graphs? Note that the diameter is at most 2. I don't fully understand the second graph of your answer. –  Yixin Cao Dec 4 '12 at 20:47
How do you think you can construct the graph $2P_3$ by clique-expanding a threshold graph? It is not a threshold graph itself (it has no isolated vertices and no vertices adjacent to all others) and there are no cliques that could have come from an expansion step. –  David Eppstein Dec 4 '12 at 21:16
My mistake. Thank you again. –  Yixin Cao Dec 4 '12 at 21:24
Graphclass: $(2P_3,C_4,P_4)$-free on –  Pål GD Jan 25 at 11:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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