On the chromatic number of multiple interval graphs and overlap graphs (Q1061131)

Let \(\chi\) (G) and \(\omega\) (G) denote the chromatic number and clique number of a graph G. In this paper it is shown that \(\chi\) can be bounded by a function of \(\omega\) for two well-known relatives of interval graphs: \(\chi\leq 2t(\omega -1)\) for \(\omega\geq 2\) for multiple interval graphs (the intersection graphs of sets which can be written as the union of t closed intervals of a line) and \(\chi \leq 2^{\omega}\omega^ 2(\omega -1)\) for overlap graphs. Also, since the determination of the chromatic number of overlap graphs and of circular-arc graphs (special 2-interval graphs) is an NP-complete problem, the proof of Theorem 1 gives a polynomial algorithm for coloring a t-interval graph G with at most 2t(\(\omega\)-1) colors.