弦グラフ
弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である(4頂点以上の誘導グラフは閉路を持たないか、弦を持つ)。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、perfect elimination orderingという頂点の順序付けが可能である」「最小頂点分離(minimal separator)(グラフを全域グラフでなくするために除去する必要最小限なグラフ)がクリークである」「木の部分木の交差グラフ(英語版)」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。
弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの木幅(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。
区間グラフは道の部分木の交差グラフであり、木の特殊な場合である。したがって、弦グラフの一種である。
スプリットグラフは、あるグラフと、その補グラフがともに弦グラフであるようなグラフである。頂点数nが増加するにつれ、弦グラフがスプリットグラフである割合は1に近づくBender, Richmond & Wormald (1985).
プトレマイオスグラフは、弦グラフの内、Distance-hereditary graphでもあるものをいう。Distance-hereditary graphとは、2頂点間の距離が、その2頂点を含む任意の連結な誘導部分グラフにおいても変化しないグラフである。 準閾値グラフはプトレマイオスグラフの一種であり、弦グラフであり、cographであるプトレマイオスグラフをいう。 ブロックグラフもプトレマイオスグラフの一種であり、任意の2つの極大クリークが少なくとも1つの頂点を共有するようなグラフである。