Some properties of 2‐threshold graphs
P. L. Hammer, N. V. R. Mahadev, Uri N. Peled · Networks · 1989
Abstract A 2‐threshold graph is defined to be the edge‐union of two threshold graphs. We prove that all chordless cycles of size at least 5 and their complements are forbidden for 2‐threshold graphs. We also obtain a sufficient condition for a 2‐threshold graph to be a comparability graph. Finally, we show that 2‐threshold graphs can have at most three cutpoints and obtain efficient algorithms to recognize, decompose and obtain a maximum stable set of 2‐threshold graphs with exactly three cutpoints.