Mixed unit interval graphs |
| |
| Authors: | Mitre C Dourado Van Bang Le Fábio Protti Dieter Rautenbach Jayme L Szwarcfiter |
| |
| Institution: | 1. Instituto de Matemática, NCE, and COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, RJ, Brazil;2. Institut für Informatik, Universität Rostock, Rostock, Germany;3. Instituto de Computação, Universidade Federal Fluminense, Niterói, RJ, Brazil;4. Institut für Optimierung und Operations Research, Universität Ulm, Ulm, Germany |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
