Title of article
Mixed unit interval graphs
Author/Authors
Dourado، نويسنده , , Mitre C. and Le، نويسنده , , Van Bang and Protti، نويسنده , , Fلbio and Rautenbach، نويسنده , , Dieter and Szwarcfiter، نويسنده , , Jayme L.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2012
Pages
7
From page
3357
To page
3363
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.
Keywords
Intersection graph , interval graph , proper interval graph , unit interval graph
Journal title
Discrete Mathematics
Serial Year
2012
Journal title
Discrete Mathematics
Record number
1600149
Link To Document