The Chromatic Number of Ordered Graphs With Constrained Conflict Graphs

Maria Axenovich, Jonathan Rollin, Torsten Ueckerdt

An ordered graph $G$ is a graph whose vertex set is a subset of integers. The edges are interpreted as tuples $(u,v)$ with $u<v$. For a positive integer $s$, a matrix $M \in \mat…