直線完全グラフ
グラフ理論において、線状完全グラフとは、線状グラフ自体が完全グラフであるグラフのことである。同様に、これはすべての奇数長単純閉路が三角形であるグラフである。[ 1 ]
グラフが線完全であるためには、その2部連結成分のそれぞれが2部グラフ、完全グラフ K 4 、または三角形グラフ K 1,1, n である必要があります。[ 2 ]これら3種類の2部連結成分はすべて完全グラフであるため、すべての線完全グラフはそれ自体が完全です。[ 1 ]同様の推論により、すべての線完全グラフはパリティグラフ、[ 3 ]メイニエルグラフ、[ 4 ]および完全に順序付け可能なグラフです。
ラインパーフェクトグラフは二部グラフを一般化したもので、最大マッチングと最小頂点被覆が同じ大きさであること、彩色指数が最大次数に等しいことなどの性質を二部グラフと共有している。[ 5 ]
参照
- 絞扼グラフ、すべての周辺サイクルが三角形であるグラフ
参考文献
- ^ a b Trotter, LE Jr. (1977)、「Line perfect graphs」、Mathematical Programming、12 (2): 255– 259、doi : 10.1007/BF01593791、MR 0457293
- ^マフレー、フレデリック（1992）「完璧な線グラフの核」、組合せ理論ジャーナル、シリーズB、55（1）：1-8、doi：10.1016/0095-8956（92）90028-V、MR 1159851 。
- ^マーティン・グレッチェル; Lovász, ラスロー; Schrijver, Alexander (1993)、「幾何学的アルゴリズムと組み合わせ最適化」、アルゴリズムと組み合わせ、第 1 巻。 2 (第 2 版)、Springer-Verlag、ベルリン、土井: 10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8、MR 1261419
- ^ Wagler, Annegret (2001), 「完全グラフにおける臨界辺と反臨界辺」, Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14–16, 2001, Proceedings , Lecture Notes in Computer Science, vol. 2204, Berlin: Springer, pp. 317– 327, doi : 10.1007/3-540-45477-2_29 , ISBN 978-3-540-42707-0、MR 1905643。
- ^ de Werra, D. (1978)、「On line-perfect graphs」、Mathematical Programming、15 (2): 236– 238、doi : 10.1007/BF01609025、MR 0509968 。
