It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
- The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{0,1\}^{n\times n}$ that can be permuted to take an upper triangular form,
- The set of perfect bipartite matchings on $n+n$ nodes consists of binary matrices $x_{ij} \in \{0,1\}^{n\times n}$ such that $\sum_i x_{ij} = \sum_j x_{ij} = 1$,
- The set of spanning trees on $n$ nodes consists of symmetric binary matrices $x_{ij} \in \{0,1\}^{n\times n}$ such that $$\sum_{i,j} x_{ij} = 2(n-1)$$ and $$\sum_{(i,j):i,j\in S}x_{ij} \leq 2(|S|-1)$$ for all proper subsets $S\subset\{1,\dots,n\}$, and
- The set of all Hamiltonian circuits through $n$ nodes consists of symmetric binary matrices $x_{ij} \in \{0,1\}^{n\times n}$ such that $$\sum_j x_{ij} = 2$$ for all $i$ and $$\sum_{i\in S, j\not\in S} x_{ij} \geq 2$$ for all proper subsets $S\subset\{1,\dots,n\}$.
I am wondering if there exists a similar representation for interval graphs, especially interval graphs of bounded chromatic number? The literature I have reviewed always deals with constructing the configuration of intervals explicitly, and I am curious if there is a natural combinatorial representation that I could use in, say, integer programming.
