Equitable coloring  of trees

日本数学会平成5年度年会応用数学分科会講演アブストラクト

宮田大輔,金子篤,徳永伸一　　グラフGの頂点を，隣接する頂点が異なる色になるようにk色で塗り分けることができるとき，グラフGはk-均等彩色可能であるという。頂点数nの木が，k-均等彩色可能であることの必要十分条件が，任意の頂点についてその頂点を含むn/kの切上げの大きさの独立点集合を含むことであることを報告した。