• 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