Interval chromatic number of an ordered graph: Difference between revisions

Revision as of 12:35, 21 March 2008

Revision as of 13:32, 21 March 2008

Line 1:

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 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>

<ref>Janos Pach, Gabor Tardos,"Forbidden Pattern and Unit Distances",page 1-9,2005,ACM.</ref>

== Difference with Chromatic 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 [[Graph]] H and it's [[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 ==