二部グラフの閉路被覆と均等彩色

頂点数が2nの平衡2部グラフは，最小次数が（n+1)/3以上であれば，全頂点を高々4つの閉路で覆えることを示した。また，頂点数nの木が，k-均等彩色可能であることの必要十分条件が，任意の頂点についてその頂点を含むn/kの切上げの大きさの独立点集合を含むことであることを示した。

慶應義塾大学大学院理工学研究科計算機科学専攻修士論文