Homomorphisms to oriented cycles |
| |
Authors: | Pavol Hell Huishan Zhou Xuding Zhu |
| |
Institution: | (1) Simon Fraser University, V5A 1S6 Burnaby, B. C., Canada |
| |
Abstract: | We discuss the existence of homomorphisms to oriented cycles and give, for a special class of cyclesC, a characterization of those digraphs that admit, a homomorphism toC. Our result can be used to prove the multiplicativity of a certain class of oriented cycles, (and thus complete the characterization of multiplicative oriented cycles), as well as to prove the membership of the corresponding decision problem in the classNP coNP. We also mention a conjecture on the existence of homomorphisms to arbitrary oriented cycles. |
| |
Keywords: | 05 C 20 05 C 99 |
本文献已被 SpringerLink 等数据库收录! |
|