On Structures and Properties of Edge-Colored Graphs and Digraphs

(G,c)を辺着色グラフ，c: E(G)→Nを辺着色写像とする．Gの任意の２点x,y∈ V(G)に対して，Gに彩色サイクルの列C_1, C_2,..., C_lで，1. x∈ V(C_1), y∈ V(C_l) かつ 2. 任意の1≦ i< lに対して，V(C_i)∩ V(C_{i+1})は空集合でない，となるものがある時，x,yはサイクル色連結であるという．パスPの端点xに接続している辺の色をc_x(P)と書く．もし，x,yを端点とする彩色パスP,Qで，c_x(P)≠c_x(Q) かつ c_y(P)≠c_y(Q)となるものがあるとき，x,yは色連結であるという．また色連結性がV(G)上の推移律を満たすとき，(G,c)は好適であるという．容易にx,yがサイクル色連結ならば常にそれらが色連結になることを確かめられる．しかしその逆の主張は必ずしも成り立たないことが知られている．(G,c)が好適であるとき，(G,c)を強好適と呼ぶ．Saadは２辺着色完全グラフが好適であることを示し，Bang-Jensen and Gutinはそれを，２辺着色完全多部グラフのあるクラスに一般化した．今回，任意の自然数k,l∈ Nに対して，任意のk辺着色l部グラフが強好適であることを示すのに成功した．また色連結性とサイクル色連結性について，以下の性質が成り立つことを示した．定理：任意のk辺着色グラフ(G,c)に対して，次の主張は同値である．１．(G,c)は色連結．２．(G,c)はサイクル色連結．３．任意の空でないGの真の部分グラフHに対して，彩色サイクルで，HとG-V(H)の両方と交差するものがある．一般に辺着色グラフは有向グラフの一般化になっているが，上の定理は有向グラフの強連結性の特徴付の一般化になっている．

(G,c)を辺着色グラフ，c: E(G)→Nを辺着色写像とする．Gの任意の２点x,y∈ V(G)に対して，Gに彩色サイクルの列C_1, C_2,..., C_lで，1. x∈ V(C_1), y∈ V(C_l) かつ 2. 任意の1≦ i< lに対して，V(C_i)∩ V(C_{i+1})は空集合でない，となるものがある時，x,yはサイクル色連結であるという．パスPの端点xに接続している辺の色をc_x(P)と書く．もし，x,yを端点とする彩色パスP,Qで，c_x(P)≠c_x(Q) かつ c_y(P)≠c_y(Q)となるものがあるとき，x,yは色連結であるという．また色連結性がV(G)上の推移律を満たすとき，(G,c)は好適であるという．容易にx,yがサイクル色連結ならば常にそれらが色連結になることを確かめられる．しかしその逆の主張は必ずしも成り立たないことが知られている．(G,c)が好適であるとき，(G,c)を強好適と呼ぶ．Saadは２辺着色完全グラフが好適であることを示し，Bang-Jensen and Gutinはそれを，２辺着色完全多部グラフのあるクラスに一般化した．今回，任意の自然数k,l∈ Nに対して，任意のk辺着色l部グラフが強好適であることを示すのに成功した．また色連結性とサイクル色連結性について，以下の性質が成り立つことを示した．定理：任意のk辺着色グラフ(G,c)に対して，次の主張は同値である．１．(G,c)は色連結．２．(G,c)はサイクル色連結．３．任意の空でないGの真の部分グラフHに対して，彩色サイクルで，HとG-V(H)の両方と交差するものがある．一般に辺着色グラフは有向グラフの一般化になっているが，上の定理は有向グラフの強連結性の特徴付の一般化になっている．