Chordal probe graphs (Q1887057)

A graph \(G=(V, E)\) is a chordal probe graph if there exists a partition \(V=P\cup N\) with a stable set \(N\) and a completion \(E'\subseteq\{uv : u\not= v\in N\}\) such that the graph \((V, E\cup E')\) is a chordal graph. Chordal probe graphs generalize probe interval graphs introduced by P. Zhang; see also [\textit{F. R. McMorris, C. Wang} and \textit{P. Zhang}, Discrete Appl. Math. 88, 315--324 (1998; Zbl 0918.05087)]. Among other initial results on chordal probe graphs, the authors prove that chordal probe graphs which are also weakly chordal can be recognized in \(O(m^2)\) time where a partition \(P\cup N\) is given or not, and \(m\) is the number of edges. The complexity of recognizing chordal probe graphs in general is still open, even in the partitioned version.