On the Recognition of Probe Graphs of Some Self-Complementary Classes of Perfect Graphs

摘要

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