Completion of the mixed unit interval graphs hierarchy

Alexandre Talon, Jan Kratochvíl

Abstract: This paper completes the structural classification of unit interval graphs by identifying the "almost-mixed" class. This class occupies the gap between standard unit interval graphs and fully mixed varieties, depending on whether intervals are open, closed, or semi-closed. The authors provide a forbidden subgraph characterization and $O(n^2)$ recognition algorithms, effectively closing the hierarchy of unit interval graphs based on interval endpoint types.

Introduction

An interval graph is an intersection graph of a set of intervals on the real line. Each vertex corresponds to an interval, and an edge exists between two vertices if their intervals overlap. When all intervals are restricted to have a unit length, the resulting class is known as unit interval graphs.

While the choice of open $(a, b)$, closed $[a, b]$, or semi-closed $[a, b)$ intervals does not affect the class of general interval graphs, it significantly impacts unit interval graphs. Restricting the allowed types of unit intervals creates distinct graph classes with varying structural properties. This paper addresses the final remaining gap in this hierarchy by defining the "almost-mixed" unit interval graph class.

The "Almost-Mixed" Class

The authors define the "almost-mixed" class, denoted as $U^{\pm, +-}$, which allows closed intervals, open intervals, and exactly one type of semi-closed interval (e.g., left-closed, right-open). Due to the symmetry of the real line, the choice between left-closed-right-open and right-closed-left-open is mathematically equivalent.

This class sits strictly between the class of unit interval graphs using only closed and open intervals ($U^{\pm}$) and the "Mixed" class ($U$) that allows all four interval types. The paper establishes the strict hierarchy: $$U^{\pm} \text{-graphs} \subsetneq U^{\pm, +-} \text{-graphs} \subsetneq U \text{-graphs}$$

Examples of forbidden subgraphs including the $K_{1,4}^*$ family.

A key insight is the "hierarchy collapse": many other combinations of interval types do not yield new classes. For instance, allowing closed intervals and both types of semi-closed intervals results in a class that collapses back into standard unit interval graphs.

Characterization and Algorithms

The structural boundaries of these classes are defined by forbidden induced subgraphs. While the "claw" graph ($K_{1,3}$) is the classic forbidden subgraph for standard unit interval graphs, the $U^{\pm, +-}$ class is characterized by more complex structures, such as the $K_{1,4}^*$ family.

The authors provide an exhaustive list of minimal forbidden induced subgraphs for the almost-mixed class. These are categorized into several families ($\mathcal{A, B, B', B'', C, C'}$). Many of these families are infinite, meaning they contain graphs of arbitrary size that follow a specific pattern.

The $R_i$ family of forbidden subgraphs, where $i$ denotes the number of triangles.

Beyond structural characterization, the paper introduces an $O(n^2)$ algorithm to recognize "almost-mixed" unit interval graphs and generate their geometric representations. The approach involves:

  1. Pruning: Removing "twin" vertices (vertices with identical neighborhoods) to simplify the graph.
  2. Representation Generation: Building a general representation using existing techniques.
  3. Transformation: Applying specific shifting rules to convert the general representation into one that fits the $U^{\pm, +-}$ class, if possible.

Conclusion

By identifying the $U^{\pm, +-}$ class and providing its complete characterization, this work effectively closes the chapter on endpoint-based hierarchies for unit interval graphs. The results show that even minor changes in interval definitions can lead to distinct graph classes, though many such variations eventually collapse into a few fundamental categories. Future research may extend these hierarchical studies to other geometric intersection models or intervals with slightly varying lengths.

Summary updated

BibTeX
@inproceedings{talon2015completion,
  author = {Alexandre Talon and Jan Kratochvíl},
  title = {{Completion of the mixed unit interval graphs hierarchy}},
  booktitle = {TAMC},
  year = {2015},
  doi = {10.1007/978-3-319-17142-5\_25},
}
Figure