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

グラフ$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)