Interval chromatic number of an ordered graph: Difference between revisions

Revision as of 03:10, 27 May 2008

Revision as of 04:40, 28 May 2008

Line 1:

IntervalIn mathematics, the '''interval [[chromatic number]]''' ''X''_<(''H'') of an [[ordered graph]] ''H,'' is the minimum number of intervals the (linearly ordered) vertex set of ''H'' can be [[partition of a set|partitioned]] into so that no two vertices belonging to the same interval are adjacent in ''H''.<ref>Janos Pach, Gabor Tardos, "Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.</ref>

== Difference with Chromaticchromatic number ==

It is interesting about interval chromatic number that it is easily computable. Indeed, by a simple greedy algorithm one can efficiently find an optimal partition of the vertex set of ''H'' into ''X''_<(''H'') independent intervals. This is in sharp contrast with the fact that even the approximation of the usual chromatic number of graph is an [[NP hard]] task.

Let ''K''(H) is the chromatic number of any ordered graph ''H''. Then for any ordered graph ''H'',

''X''_<(''H'') ≥ K(''H'').

One thing to be noted, for a particular [[Graphgraph]] ''H'' and it'sits [[isomorphic]] graphs the [[chromatic number]] is same, but the interval chromatic number may differ. Actually it depends upon the ordering of the vertex set.

== Reference ==

<references/>

[[Category:Graph coloring]]

[[Category:Graph theory]]