グラフの3彩色について

**１３２人目の素数さん** · 2025/02/27(木) 11:16:52.50

頂点n個の完全グラフを3彩色可のグラフにするため辺をk本切断する操作を考える。
この時kの最小値をnで表せないかな？
対角線だけ残したグラフと周だけ残したグラフの二つは自明だけど…

**１３２人目の素数さん** · 2025/02/28(金) 09:12:37.30

なんか知らんが頑張れ

**１３２人目の素数さん** · 2025/03/01(土) 10:42:16.92

やるかー
時間かかるけどプログラムで計算して表に著して観てみるか
頂点4の時は1本切ればいいけどそれ以降が不透明なんよな
式にできれば帰納法で証明できるだろうからとりあえずそこまで頑張ってみるぜ

**１３２人目の素数さん** · 2025/03/01(土) 11:02:29.53

ちなみにchatGPT先生曰くk≒n^2/3らしい。
近似になるのがなんでなのかは分からん。
nk平面における分布をまとめるとそれらしくなるのかもしれないけど。
公式が欲しい。

**１３２人目の素数さん** · 2025/03/01(土) 22:11:01.33

4^2/3は1に全然近くないが

**１３２人目の素数さん** · 2025/03/03(月) 21:19:29.35

nが3の倍数のときn(n-3)/6
それ以外のとき(n-1)(n-2)/6