Martin C. Golumbic
Caesarea Rothschild Institute and
Department of Computer Science
University of Haifa, Mt.
Title: A characterization of chain
probe graphs
Abstract:
A chain probe graph is a graph that admits an
independent set S of
vertices and a set F of pairs of elements of
S such that G+F is a chain
graph (i.e., a {2K_2}-free bipartite
graph). We show that chain probe
graphs are exactly the bipartite graphs
that do not contain as an induced
subgraph a member of a family of six
forbidden subgraphs, and deduce an
O(n^2) recognition algorithm.
(Joint work with Frederic Maffray and Gregory Morel, Laboratoire
G-SCOP,
INPG,