Interval chromatic number of an ordered graph: Difference between revisions

Revision as of 05:33, 8 April 2008

Latest revision as of 16:57, 27 July 2025

(15 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Concept in the mathematics field of graph theory}}

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>

{{uncategorizedone source |date=April 20082024}}

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[[János 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 [[Graph (discrete mathematics)|graph]] ''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==

<references/>

{{uncategorized|date=April 2008}}

[[Category:Graph coloring]]

{{graph-stub}}