区間グラフ
arXiv:1109.6675. Bibcode: 2011arXiv1109.6675B.
↑ Klavík, Pavel; Otachi, Yota; Šejnoha, Jiří (14 October 2015). "On the Classes of Interval Graphs of Limited Nesting and Count of Lengths". arXiv:1510.03998 [cs.DM]。
↑ Cohen (1978, pp. ix-10)
↑ Cohen (1978, pp. 12–33)
↑ Bar-Noy et al. (2001).
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, ISBN 0-262-03293-7
↑ Zhang et al. (1994).
↑ Golumbic & Shamir (1993).
↑ Villanger et al. (2009).
↑ Bliznets et al. (2014).
↑ Bodlaender (1998).
正式には、区間グラフは区間の族
Si, (i = 0, 1, 2, ... )
に対し、頂点 vi をそれぞれ1個ずつ与え、 SiとSjが空集合ではない共通部分(交差)を持つ場合にのみ、vi と vj を辺で結んだ、無向グラフである。つまり、グラフ G の辺集合 E(G)は
E(G) = {{vi, vj} | Si ∩ Sj ≠ ∅}.
である。