首页 | 本学科首页   官方微博 | 高级检索  
     


Kernels by properly colored paths in arc-colored digraphs
Authors:Yandong Bai  Shinya Fujita  Shenggui Zhang
Affiliation:1. Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an 710129, China;2. International College of Arts and Sciences, Yokohama City University, Yokohama 236-0027, Japan
Abstract:A kernel by properly colored paths of an arc-colored digraph D is a set S of vertices of D such that (i) no two vertices of S are connected by a properly colored directed path in D, and (ii) every vertex outside S can reach S by a properly colored directed path in D. In this paper, we conjecture that every arc-colored digraph with all cycles properly colored has such a kernel and verify the conjecture for digraphs with no intersecting cycles, semi-complete digraphs and bipartite tournaments, respectively. Moreover, weaker conditions for the latter two classes of digraphs are given.
Keywords:Kernel  Kernel by properly colored (monochromatic, rainbow) paths
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号