查看文章

In this paper we consider the recognition of some probe graph classes. Given a class of graphs , a graph G is a probe graph of if its vertices can be partitioned into a set ℙ of probes and an independent set ℕ of nonprobes, such that G can be extended to a graph of by adding edges between certain nonprobes. We show that there are polynomial-time recognition algorithms for probe cographs, probe P ₄-reducible graphs, probe P ₄-sparse graphs, and probe splitgraphs.