内周 (グラフ理論)

任意の正の整数 g と χ に対して、内周が少なくとも g であり、彩色数が少なくとも χ であるようなグラフが存在する：例えば、グレッチグラフ（英語版）はトライアングルフリーで彩色数が 4 であり、そのグラフを構成するためのミシェルスキアン（英語版）構成法を繰り返すことで、任意の大きさの彩色数を備えるトライアングルフリーなグラフを構成することが出来る。ポール・エルデシュは、確率的手法（英語版）を用いて、初めてその一般的な結果を証明した^[4]。厳密に言うと彼は、各辺が含まれるかどうかが確率 n^{(1 − g)/g} で独立に決定されるような頂点数 n のランダムグラフ（英語版）は、n が無限大へと向かうにつれて 1 に近付くような確率に対して、長さが g 以下であるような閉路を多くとも n/2 個含むが、大きさが n/2k であるような独立集合は含まない、ということを証明した。したがって、それぞれの短閉路（short cycle）から一つ頂点を取り除くことにより、内周が g より大きく、各彩色の同色集合が小さいためにどのような彩色においても少なくとも k 色が必要となるような、より小さいグラフが得られる。

グラフの奇内周（odd girth）および偶内周（even girth）とは、それぞれ最小の奇閉路および偶閉路の長さのことを言う。

非自明な閉路の最小の長さを考えることで、内周は、シストリック幾何学（英語版）における1-シストールやより高位のシストールとしての自然な一般化が可能となる。

1. ↑ R. Diestel, Graph Theory, p.8. 3rd Edition, Springer-Verlag, 2005
2. ↑ Girth -- Wolfram MathWorld, https://mathworld.wolfram.com/Girth.html 
3. ↑ Brouwer, Andries E., Cages, http://www.win.tue.nl/~aeb/drg/graphs/ . Electronic supplement to the book Distance-Regular Graphs (Brouwer, Cohen, and Neumaier 1989, Springer-Verlag).
4. ↑ Erdős, Paul (1959), “Graph theory and probability”, Canadian Journal of Mathematics 11: 34–38, doi:10.4153/CJM-1959-003-9 .

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト ラプラシアン行列
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合 マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 最大カット問題 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ