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 is a set of vertices of such that (i) no two vertices of are connected by a properly colored directed path in , and (ii) every vertex outside can reach by a properly colored directed path in . 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 等数据库收录! |
|