Loading article…
数学において、接続ポーズセットまたは接続順序は、無向グラフの頂点と辺の間の接続関係を表す半順序集合の一種です。グラフGの接続ポーズセットには、 G内の各頂点または辺の要素があります。このポーズセットでは、 x = yであるか、 xが頂点、yが辺、xがyの端点である場合に限り、順序関係x ≤ yが存在します。
例
例として、奇数個の要素を持ち、交互の順序関係a < b > c < d ... を持つジグザグ posetまたはフェンスは、パス グラフの接続 poset です。
プロパティ
空でないグラフのすべての接続ポセットの高さは 2 です。その幅は、エッジの数と非循環接続コンポーネントの数の合計に等しくなります。
入射ポセットは、その順序次元と、その基になるグラフの特性との関係について特に研究されてきた。連結グラフGの入射ポセットは、 G がパスグラフである場合に限り、順序次元が最大でも 2 であり、 G が最大でも平面である場合に限り、順序次元が最大でも 3 である (シュナイダーの定理)。[1]ただし、入射ポセットの順序次元が 4 のグラフは稠密である可能性があり[2] 、彩色数が無制限である可能性がある。[3] n頂点のすべての完全グラフ、および拡張によりn頂点のすべてのグラフには、順序次元がO (log log n ) の入射ポセットがある。[4]入射ポセットが高次元である場合、すべての小さな木の発生ポセットのコピーが、サブ順序またはサブ順序の双対として含まれている必要がある。[5]
参照
- 折れ線グラフ、関連する構成
参考文献
- ^ Schnyder, W. (1989)、「平面グラフとポセット次元」、Order、5 (4): 323–343、doi :10.1007/BF00353652、S2CID 122785359。
- ^ アグナルソン、ゲイル; フェルスナー、ステファン; トロッター、ウィリアム T. (1999)、「境界次元のグラフの最大辺数と環理論への応用」、離散数学、201 (1–3): 5–19、doi : 10.1016/S0012-365X(98)00309-4、MR 1687854。
- ^ Trotter, William T.; Wang, Ruidong (2014)、「発生ポセットとカバーグラフ」、Order、31 (2): 279–287、arXiv : 1308.2471、doi :10.1007/s11083-013-9301-9、S2CID 17560524。
- ^ Hoşten, Serkan; Morris, Walter D. Jr. (1999)、「完全グラフの順序次元」、離散数学、201 (1–3): 133–139、doi :10.1016/S0012-365X(98)00315-X、MR 1687882。
- ^ ブライトウェル、グラハム R.; トロッター、ウィリアム T. (1994)、「大規模次元のポセットにおける木の発生ポセット」、オーダー、11 (2): 159–167、doi :10.1007/BF01108600、MR 1302404、S2CID 120777046。