The Chromatic Number of Ordered Graphs With Constrained Conflict Graphs

Abstract

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 {\mathbb{Z}}^{s\times 4}$, and a vector $\mathbf{p}=(p,\dots ,p)\in {\mathbb{Z}}^s$ we build a conflict graph by saying that edges $(u,v)$ and $(x,y)$ are conflicting if $M(u,v,x,y{)}^{\top }\ge \mathbf{p}$ or $M(x,y,u,v{)}^{\top }\ge \mathbf{p}$, where the comparison is componentwise. This new framework generalizes many natural concepts of ordered and unordered graphs, such as the page-number, queue-number, band-width, interval chromatic number and forbidden ordered matchings. For fixed $M$ and $p$, we investigate how the chromatic number of $G$ depends on the structure of its conflict graph. Specifically, we study the maximum chromatic number $X_{\text{cli}}(M,p,w)$ of ordered graphs $G$ with no $w$ pairwise conflicting edges and the maximum chromatic number $X_{\text{ind}}(M,p,a)$ of ordered graphs $G$ with no $a$ pairwise non-conflicting edges. We determine $X_{\text{cli}}(M,p,w)$ and $X_{\text{ind}}(M,p,a)$ exactly whenever $M$ consists of one row with entries in $\{-1,0,+1\}$ and moreover consider several cases in which $M$ consists of two rows or has arbitrary entries from $\mathbb{Z}$.

33 pages, 4 figures