区間グラフ
k +1 段の入れ子になっていない区間グラフを、k -重であると呼ぶ。真区間グラフは被覆する区間を持たないため、 1-重区間グラフである。
ある3つの頂点に対して、そのうち2つを含むが3つめの頂点に隣接する頂点を含まないパスが存在する場合、そのグラフ G はasteroidal tripleを形成する。また、asteroidal triple を含まない場合、グラフはAT-freeという。 区間グラフの初期の特徴付けは以下のようなものであった。
区間グラフは以下のグラフと同値である。
AT-freeである弦グラフ
G の極大クリークが、i < k ならば任意のv ∈ Mi ∩ Mk であるようにM1, M2, ..., Mk と順序付けができるグラフ(i ≤ j ≤ kなるv ∈ Mj についても同様)。
極大クリークに含まれる辺の被覆が、クリークパス表現に配置することができるグラフ。
誘導部分グラフとして閉路グラフ C4 を含まず、補グラフが比較可能グラフではないグラフ。
他にも、区間グラフは様々な特徴付けがなされている。
真区間グラフは、被覆するような区間が存在しない区間グラフを指す。図は区間Bが区間Aに被覆され、区間Eは区間Dに、そして更に区間Dは区間Cに被覆されているため、真区間グラフではない。 単位区間グラフはすべての区間が長さ1であるような区間グラフである。同一区間を持たない単位区間グラフは、真区間グラフである。真区間グラフが常に単位区間グラフであるわけではないが、単位区間グラフは真区間グラフである。真区間グラフは、クローフリーグラフであり、真区間グラフはクローフリー区間グラフである。しかし、区間グラフではないクローフリーグラフも存在する。
区間グラフが、 q 個の例外区間を除き、他の区間に被覆される区間を持たない場合、q-真区間グラフであると呼ぶ。この表記では、真区間グラフは 0-真区間グラフである。 図では、B, D, Eの3つが被覆されており、この3つ以外は真区間グラフを満たすため、3-真区間グラフである。