Two characterizations of chain partitioned probe graphs

Abstract

Chain graphs are exactly bipartite graphs without induced $2K_2$ (a graph with four vertices and two disjoint edges). A graph $G=(V,E)$ with a given independent set $S\subseteq 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$. %there exists a set $E^{\prime }\subseteq \left(\genfrac{}{}{0ex}{}{S}{2}\right)$ such that the graph $G^{\prime }=(V,E\cup E^{\prime })$ is a chain graph. 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^{\ast }$ 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.

Cited by in corpus (1)

• Good characterizations and linear time recognition for 2-probe block graphs