グラフの3彩色について

グラフの3彩色について (6ﾚｽ)
上下前次 1-新

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

2: 02/28(金)09:12 ID:EHAzzIyG(1) AAS
なんか知らんが頑張れ

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

4: 03/01(土)11:02 ID:fb64tq5C(2/2) AAS
ちなみにchatGPT先生曰くk≒n^2/3らしい。
近似になるのがなんでなのかは分からん。
nk平面における分布をまとめるとそれらしくなるのかもしれないけど。
公式が欲しい。

5: 03/01(土)22:11 ID:UQYv3ub4(1) AAS
4^2/3は1に全然近くないが

6: 03/03(月)21:19 ID:4GEovj34(1) AAS
nが3の倍数のときn(n-3)/6
それ以外のとき(n-1)(n-2)/6