Interval coloring

Interval coloring --- интервальная раскраска.

An interval coloring of a weighted graph [math]\displaystyle{ (G,w) }[/math] maps each vertex [math]\displaystyle{ x }[/math] to an open interval [math]\displaystyle{ I_{x} }[/math] on a real line, of width [math]\displaystyle{ w(x) }[/math], such that adjacent vertices are mapped to disjoint intervals. The total width of an interval coloring is defined to be [math]\displaystyle{ |\cup_{x}I_{x}| }[/math]. The interval chromatic number [math]\displaystyle{ \chi(G,w) }[/math] is the least total width needed to color the vertices with intervals.

A graph [math]\displaystyle{ G }[/math] is called superperfect if for every non-negative weight function [math]\displaystyle{ w }[/math], [math]\displaystyle{ \Omega(G,w) = \chi(G,w) }[/math].