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}）cov（c_i+1}）cove（c_i+1}）不是一个空的颜色。将连接到路径p的端点x的边的颜色作为c_x（p）。如果有一个颜色路径p，q，y作为端点，并且有一个c_x（p）≠c_x（q）和c_y（p）≠c_y（q），则x，y被称为颜色串联。此外，当颜色连接满足V（g）的过渡规则时，据说是合适的。很容易确保，如果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