Bipartite Unit Probe Interval Graphs

Document Type

Article

Publication Title

Australasian Journal of Combinatorics

Department

Mathematics

ISSN

1034-4942

Volume

52

First Page

19

Last Page

31

Publication Date

1-1-2012

Abstract

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.

Link to Full Text

Share

COinS