On Structures and Properties of Edge-Colored Graphs and Digraphs

关于有色图和有向图的结构和性质

• 批准号: 18K03402
• 负责人: 善本 潔
• 金额: $ 2.83万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K03402/
• 关键词: 辺着色グラフ; 完全グラフ; 色連結; サイクル色連結; 有向グラフ; 強連結; 彩色サイクル鎖; 完全多部グラフ; グラフ理論; 連結性; 辺彩色サイクル; ハミルトンサイクル; ２因子; 偶全域木; 正則グラフ; 非２部性; Bermond-Thomassen予想; essentially digraph; 最大単色次数; 有向２部グラフ; 多部トーナメント; サイクル; 最小色次数; 辺着色; ラムゼー理論; Gallai分割

(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)の両方と交差するものがある．一般に辺着色グラフは有向グラフの一般化になっているが，上の定理は有向グラフの強連結性の特徴付の一般化になっている．

C: e (G), N (C), G, G, y ∈ V (G), G, C, G, C, G, G, C, C Any "1" i&lt L, V (Centri) V (C1N1}) empty set, please contact with the color link. The end point is connected with the color signal c _ x (P), and the color connection is called PQ. Cedar x (P) ≠ cedar x (Q). Clocky (P) ≠ clocky (P) ≠ centery (Q). The law of motion on the color connection V (G) is different. (Ggramec) it's easy to make sure that you don't know what you're going to do. (Ggramec) it's easy to make sure that you don't know if you don't know what's wrong with you. (Ggramec) make a good call. Saad 2 coloring is complete, Bang-Jensen and Gutin coloring is complete, and 2 coloring is complete. This time, any number of natural numbers, kd1 ∈ N, is very general. Any k coloring system will show that the color connection is successful. The following properties will be shown as follows. Theorem: any k shading device (GMEC) color link The secondary primary is the same as the color link. (Ggramec) the color link is .2. (Ggramec) the color link is the same as the color link. 3. Any empty image is the same as that of the real part, the color is the same as the other, and the color is the same as that of the other. General coloring is directed towards the generalization of the color. In the previous theorem, we have directed data to strengthen the properties of the property and pay the generalization.

项目成果

Structures of edge-colored graphs

边色图的结构

• 发表时间: 2018
• 作者: Sho Suda;篠原雅史;善本潔
• 通讯作者: 善本潔

Disjoint properly colored cycles in edge-colored complete bipartite graphs

• DOI: 10.1016/j.disc.2022.113095
• 发表时间: 2023-01
• 期刊: Discret. Math.
• 作者: Kiyoshi Yoshimoto

On structures of sub bipartite tournaments

论亚双边锦标赛的结构

• 发表时间: 2019
• 作者: Masashi Shinohara;Sho Suda;善本潔
• 通讯作者: 善本潔

辺着色された完全２部グラフの構造について

关于边有色完全二部图的结构

• 发表时间: 2018
• 作者: Ozeki Kenta;Zamfirescu Carol T.;篠原雅史;Sho Suda;善本潔
• 通讯作者: 善本潔

A complete bipartite graph without properly colored cycles of length four

• DOI: 10.1002/jgt.22480
• 发表时间: 2019-07
• 期刊: Journal of Graph Theory
• 影响因子: 0.9
• 作者: Roman Cada;K. Ozeki;Kiyoshi Yoshimoto