必须始终连接间隔图吗？

Question

我们知道：

形式上，区间图是一族间隔的交集图。此外，它有一个顶点用于集合中的每个区间，以及每对顶点之间的链接/边对应于相交的间隔。

但问题是：间隔图可以断开连接还是必须始终连接？

请看图： 如果是间隔或不？

http://s13.postimg.org/u320a7scn/Screenshot_3.jpg

Answer 1

有一个时间间隔曲线图是一个连通图没有要求。区间图的形式定义及其构建方式不需要连通性。

Here是其论述了断开间隔曲线图（重点煤矿）纸的例子：

Bodlaender提供用于 对完成的着色问题的NP完全为断开cographs和间隔的证明 图并延伸他的结果为连接这样的图表。他的证明 还建立了断开间隔图和cographs的和谐着色问题 的NP硬度。 [012] 尽管和谐着色问题对于 断开的区间图是NP完全的，但连通区间图的问题的复杂性并不简单。 [...]

-Asdre，Ionnidou an Nikolopoulos，和谐着色问题是NP完全的区间和置换图，ScienceDirect。