K4の対辺をつなぐ話(2)

前、こういうのを考えて、最大クリーク数もなんとなく半分になりそうって書いたんだけど、
kousuke.hatenablog.com

それって式にするとこういうことになるのかな?
 \chi(f(K_n)) = \lfloor \frac{\chi(K_n) }{2} \rfloor

fは G(V,E)の辺を頂点にして、 e_i \cup e_j K_4の時に辺とするような変換。
完全グラフについては証明できそうだけどな。


一般のグラフでも下記の形で成り立つとすれば
 \chi(f(G)) = \lfloor \frac{\chi(G) }{2} \rfloor

これを繰り返して、最大クリーク数が 2^n \le \chi(G) \lt 2^{n+1}の範囲で求められそうとおもったよ。