４，全彩色 グラフGの全彩色とは、Gの隣接するどの2元、または接続するどの2元も異なる色を持つようなGの元(頂点と辺)に色を付けることである。k個の色を用いる全彩色をk-全彩色という。グラフGに対して、k-全彩色が存在するときGはk-全彩色可能であるという…

３，辺彩色 グラフGの隣接する辺が異なる色になるように、グラフGの各辺に色をつけることを、Gの辺彩色といい、k個の色が使われているとき、それをk-辺彩色という。グラフGに対して、k-辺彩色が存在するときGはk-辺彩色可能であるという。Gがk-辺彩色可能で…

２、線グラフと全グラフ グラフGにおいて、頂点集合E(G)を持ち、その中の2頂点は、G内の隣接する2辺であるとき、かつそのときに限って隣接するようなグラフをGの線グラフといいL(G)で表す。 グラフGの全グラフT(G)とは、集合V(G)⋃E(G)と1対1対応する頂点集合…

(注意)完全グラフと全彩色予想の内容や定理の証明は「グラフ理論序説」からお借りしている部分が多いです。 １，因子分解 グラフHがグラフGの部分グラフであるとは、Hが V(H)がV(G)の部分集合 かつ E(H)がE(G)の部分集合 を満たすグラフのことである。特に、…