区间图必须始终连接吗？

Question

我们知道：

从形式上讲，区间图是区间.Moreover族的一类交图，它对集合中的每个区间都有一个顶点，并且对应于相交的区间的每一对顶点之间都有一个链接/边。

但问题是:区间图是不连通的，还是必须总是连通的？

请看图:是区间还是非区间？

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

Answer 1

区间图不要求是连通图。区间图的形式定义以及它的构造方式不需要连通性。

Here是一个讨论不连通区间图(重点是我的)的论文的例子：

Bodlaender证明了不连通余图和区间图的配对完全着色问题的NP-完备性，并将他的结果推广到连通这类图。他的证明还建立了不连通区间图、和余图的调和着色问题的NP难。..。相反，尽管对于不连通区间图，调和着色问题是NP完全的，但对于连通区间图，这个问题的复杂性并不是简单的。..。

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