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
项目状态：
已结题

项目摘要

(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 和 Gutin 将其推广到一类双面彩色完整多部分图。这次，我们成功地证明了对于任何自然数 k,l∈N，任何 k 边彩色 l 子图都是非常合适的。我们还表明以下属性适用于颜色连接和循环颜色连接。定理：对于任何 k 边彩色图 (G,c)，以下断言是等价的。 1. (G,c) 是颜色连接。 2. (G,c)是循环颜色连接。 3.对于非空 G 的任何真子图 H，都存在一个与 H 和 G-V(H) 相交的着色循环。一般来说，边有色图是有向图的推广，但上述定理是具有强连通性的有向图的推广。

项目成果

期刊论文数量（17）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Structures of edge-colored graphs

边色图的结构

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
Sho Suda;篠原雅史;善本潔
通讯作者：
善本潔

Disjoint properly colored cycles in edge-colored complete bipartite graphs

DOI：
10.1016/j.disc.2022.113095
发表时间：
2023-01
期刊：
Discret. Math.
影响因子：
0
作者：
Kiyoshi Yoshimoto
通讯作者：
Kiyoshi Yoshimoto

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

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

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
Ozeki Kenta;Zamfirescu Carol T.;篠原雅史;Sho Suda;善本潔
通讯作者：
善本潔

On structures of sub bipartite tournaments

论亚双边锦标赛的结构

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
Masashi Shinohara;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
通讯作者：
Roman Cada;K. Ozeki;Kiyoshi Yoshimoto

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

善本潔其他文献

2-factors in claw-free graphs, European Conference on Combinatorics

无爪图中的 2 因子，欧洲组合学会议

DOI：
发表时间：
2011
期刊：
影响因子：
0
作者：
千葉周也;R. Cada;善本潔;Hiroki Masuda;Rie Natsui;夏井利恵;H. Sakai and B. Velickovic;S. Chiba;増田弘毅;H. Sakai;増田弘毅;S. Chiba
通讯作者：
S. Chiba