Interval coloring

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

Definition and basic properties

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

Since the parts of an interval coloring are independent sets:

${\displaystyle \chi _{<}(H)\geq \chi (H)}$,

where ${\displaystyle \chi (H)}$ is the ordinary chromatic number.^[2]

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

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 ${\displaystyle H}$ into ${\displaystyle \chi _{<}(H)}$ independent intervals.^[1] 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 ${\displaystyle 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.^[2]

Extremal theory

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

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

${\displaystyle ex_{<}(n,H)=\left(1-{\frac {1}{\chi _{<}(H)-1}}\right){\binom {n}{2}}+o(n^{2})}$

This theorem naturally extends to families ${\displaystyle {\mathcal {H}}}$ of forbidden ordered subgraphs with:^[1]

${\displaystyle \chi _{<}({\mathcal {H}}):=\min\{\chi _{<}(H)\mid H\in {\mathcal {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.^[1] These can be represented by zero-one matrices where the vertices are enumerated as ${\displaystyle v_{1}<v_{2}<\ldots <v_{n}<v_{n+1}<\ldots <v_{n+m}}$ such that every edge connects some ${\displaystyle v_{i}}$ with ${\displaystyle i\leq n}$ to some ${\displaystyle v_{j}}$ with ${\displaystyle j>n}$.^[1]

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.^[1]

See also

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