Interval chromatic number of an ordered graph: Difference between revisions

Revision as of 12:35, 21 March 2008

Latest revision as of 16:57, 27 July 2025

(18 intermediate revisions by 16 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.

{{one source |date=April 2024}}

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>[[János Pach]], Gabor Tardos, "Forbidden Pattern and Unit Distances", page 1-9, 2005, ACM.</ref>

== Difference with Chromaticchromatic number ==

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

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.

== Difference with Chromatic number ==

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

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.

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

One thing to be noted, for a particular [[Graph (discrete mathematics)|graph]] ''H'' and its [[isomorphic]] graphs the [[chromatic number]] is same, but the interval chromatic number may differ. Actually it depends upon the ordering of the vertex set.

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

X_<(H) ≥ K(H).

== Reference References==

<references/>

[[Category:Graph coloring]]

{{graph-stub}}