Bipartite Unit Probe Interval Graphs
Australasian Journal of Combinatorics
A graph is a probe interval graph (PIG) if its vertices can be partitioned into probes and nonprobes with an interval assigned to each vertex so that vertices are adjacent if and only if their corresponding intervals intersect and at least one of the vertices is a probe. When all intervals have the same length (or equivalently, no interval contains another properly) the graph is a unit probe interval graph. We characterize, via a list of minimal forbidden induced subgraphs, and no a priori partition of vertices into probes and nonprobes, the class of bipartite unit probe interval graphs and present a linear time recognition algorithm for them which is based on this characterization.
Brown, D. E.,
Langley, L. L.
Bipartite Unit Probe Interval Graphs.
Australasian Journal of Combinatorics, 52, 19–31.