Two characterizations of chain partitioned probe graphs

摘要

Chain graphs are exactly bipartite graphs without induced 2AS (a graph with four vertices and two disjoint edges). A graph G = (V, E) with a given independent set S C V (a set of pairwise non-adjacent vertices) is said to be a chain partitioned probe graph if G can be extended to a chain graph by adding edges between certain vertices in S. In this note we give two characterizations for chain partitioned probe graphs. The first one describes chain partitioned probe graphs by six forbidden subgraphs. The second one characterizes these graphs via a certain "enhanced graph": G is a chain partitioned probe graph if and only if the enhanced graph G~* is a chain graph. This is analogous to a result on interval (respectively, chordal, threshold, trivially perfect) partitioned probe graphs, and gives an O(m~2)-time recognition algorithm for chain partitioned probe graphs.