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.


1 Answer 1


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.

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.

  • $\begingroup$ 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. $\endgroup$
    – Yixin Cao
    Dec 4, 2012 at 20:47
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 4, 2012 at 21:16
  • 2
    $\begingroup$ Graphclass: $(2P_3,C_4,P_4)$-free on graphclasses.org. $\endgroup$
    – Pål GD
    Jan 25, 2015 at 11:38

Your Answer

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

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