# Does this graph class have a name ?

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 graphclasses.org.

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 graphclasses.org.
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.
• 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. Dec 4, 2012 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. Dec 4, 2012 at 21:16
• Graphclass: $(2P_3,C_4,P_4)$-free on graphclasses.org. Jan 25, 2015 at 11:38