An algorithm for equitable coloring of bipartite graphs

最大次数が高々kであるようなグラフをO(kn2）ステップで均等(k+1)-彩色するアルゴリズムが知られているが、グラフを連結二部グラフに限れば、自明な例外を除き、O(kn)ステップでk-均等彩色するアルゴリズムが存在することを示した。

千葉商大紀要、第53巻第1号、183-191