完璧な線グラフ

グラフ理論において、線完全グラフとは、線グラフが完全グラフであるグラフのことである。言い換えれば、これはすべての奇数長の単純サイクルが三角形であるグラフである。^{[ 1 ]}

グラフが線完全であるのは、その各二連結成分が二部グラフ、完全グラフK ₄、または三角形ブックK _{1,1, n}である場合に限る。^{[ 2 ]}これら 3 種類の二連結成分はすべてそれ自体が完全グラフであるため、すべての線完全グラフはそれ自体が完全である。^{[ 1 ]}同様の推論により、すべての線完全グラフはパリティグラフ、^{[ 3 ]}メイニエルグラフ、^{[ 4 ]}および完全順序付け可能グラフである。

線完全グラフは二部グラフを一般化したもので、最大マッチングと最小頂点被覆が同じサイズであること、および彩色指数が最大次数に等しいという特性を共有している。^{[ 5 ]}

• 絞殺グラフとは、すべての周辺サイクルが三角形であるグラフのことである。