Interval coloring

In graph theory, the interval chromatic number ${\chi }_{<}(H)$ of an ordered graph $H$ is the minimum number of intervals the (linearly ordered) vertex set of $H$ can be partitioned into so that no two vertices belonging to the same interval are adjacent in $H$.

Definition and basic properties

An ordered graph is a graph $G$ together with a specified linear ordering on its vertex set $V(G)$. In an ordered graph $H$, an interval coloring is a partition of $V(H)$ into independent sets of consecutive vertices (called intervals or parts). The interval chromatic number ${\chi }_{<}(H)$ is the minimum number of parts in any interval coloring of $H$.

Since the parts of an interval coloring are independent sets:

${\chi }_{<}(H)\ge \chi (H)$,

where $\chi (H)$ is the ordinary chromatic number.

An ordered graph is called interval k-chromatic (or k-ichromatic) if ${\chi }_{<}(H)=k$.

Computational complexity

It is of particular interest that the interval chromatic number is easily computable. By a simple greedy algorithm, one can efficiently find an optimal partition of the vertex set of $H$ into ${\chi }_{<}(H)$ independent intervals. This is in sharp contrast with computing the usual chromatic number of a graph, where even finding an approximation is an NP hard task.

For a given graph $H$ and its isomorphic graphs, the chromatic number remains the same, but the interval chromatic number may differ depending on the ordering of the vertex set.

Extremal theory

Pach and Tardos proved a fundamental theorem relating the interval chromatic number to extremal graph theory:

For any ordered graph $H$, the maximum number of edges that an $H$-free ordered graph with $n$ vertices can have is:

$e{x}_{<}(n,H)=(1-\frac{1}{{\chi }_{<}(H)-1})(\genfrac{}{}{0ex}{}{n}{2})+o(n^2)$

This theorem naturally extends to families ${\mathscr{H}}$ of forbidden ordered subgraphs with:

${\chi }_{<}({\mathscr{H}}):=\min \{{\chi }_{<}(H)\mid H\in {\mathscr{H}}\}$

Relation to forbidden patterns

The interval chromatic number plays a crucial role in forbidden pattern problems for ordered graphs and zero-one matrices. For a 2-ichromatic ordered graph, the extremal problem becomes particularly interesting, as the quadratic term vanishes in the extremal function formula. These can be represented by zero-one matrices where the vertices are enumerated as $v_1<v_2<\dots <v_n<v_{n+1}<\dots <v_{n+m}$ such that every edge connects some $v_i$ with $i\le n$ to some $v_j$ with $j>n$.

The forbidden pattern problems connect to several problems in discrete geometry, including the unit distance graph problem, the planar segment-center problem, and the finding of Davenport–Schinzel sequences.

See also

• Ordered graph
• Graph coloring
• Ramsey theory
• Extremal graph theory