Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648188 | Discrete Mathematics | 2012 | 7 Pages |
Abstract
The class of intersection graphs of unit intervals of the real line whose ends may be open or closed is a strict superclass of the well-known class of unit interval graphs. We pose a conjecture concerning characterizations of such mixed unit interval graphs, verify parts of it in general, and prove it completely for diamond-free graphs. In particular, we characterize diamond-free mixed unit interval graphs by means of an infinite family of forbidden induced subgraphs, and we show that a diamond-free graph is mixed unit interval if and only if it has intersection representations using unit intervals such that all ends of the intervals are integral.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Mitre C. Dourado, Van Bang Le, Fábio Protti, Dieter Rautenbach, Jayme L. Szwarcfiter,