| 词条 | Interval chromatic number of an ordered graph |
| 释义 |
In 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 partitioned into so that no two vertices belonging to the same interval are adjacent in H.[1] Difference with chromatic numberIt 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 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. References1. ^János Pach, Gabor Tardos, "Forbidden Pattern and Unit Distances",page 1-9,2005,ACM. 1 : Graph coloring |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。