2017年7月1日土曜日

最大平均次数と彩色数について

グラフ$G$に対して



を$G$の最大平均次数 (maximum average degree) と言います.  ここでグラフ$H$に対し$||H||$は$H$の辺数, $|H|$は$H$の頂点数を表します.
頂点$v$に対して$d(v)$で$v$の次数を表すことにすると, 握手補題より$2||H||=\sum_{v\in V(H)} d(v)$となるので, $\frac{2||H||}{|H|}$は$H$の平均次数を表しています. この値はグラフの「疎っぽさ」を表すような値になっていて, 色々と興味深い結果が知られています. 実は最小カットを二分探索の判定として用いることによって多項式時間でこの値を計算することが出来ます.

$\mathrm{mad}(G)$はグラフ理論の有名な本Sparistyにも重要な指標の一つとして紹介されていて, 次のような事実が(証明なしに)紹介されています.

$\chi(G)\leq \lfloor \mathrm{mad}(G) \rfloor+1$.

つまり$\mathrm{mad}(G)$を使って彩色数$\chi(G)$を上から抑えることができます. 非自明な感じがするので今回はこの事実の証明を載せたいと思います. 内容としては$\chi(G)\leq \mathrm{mad}(G) +1$を示しています(床関数をとっても本質的には変わらないので).

(この証明は私が考えたものなので, 他にもっとスマートな証明を知っている方がいらしたら教えていただければ幸いです).







[1] A Fast Parametric Maximum Flow Algorithm and Applications, G. Gallo, M.D. Grigoriadis, R. E. Tarjan (1986)

0 件のコメント:

コメントを投稿

解の個数を減らす帰着 (Valiant--Vaziraniの定理)

2月に 冬のLA に参加してこれまで5,6年くらい常に取り組みようやく身を結んだ共同研究を発表してきました. 2月のLAではD2辺りからずっと取り組んでいた個人的未解決問題がある程度解決できたことについて発表させていただきます。 — Nobutaka Shimizu (@kn...