CHARACTERIZATION OF THE HOMOMORPHIC PREIMAGES OF CERTAIN ORIENTED CYCLES

被引：4

作者：

ZHOU, HS

机构：

来源：

SIAM JOURNAL ON DISCRETE MATHEMATICS | 1993年 / 6卷 / 01期

关键词：

DIGRAPH; BASIC CYCLE; HOMOMORPHISM; HOMOMORPHIC PREIMAGE; NP; CONP;

D O I：

10.1137/0406007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The classes of digraphs that can be homomorphically mapped to certain oriented cycles are characterized by the forbidden homomorphic preimages. This characterization can be used to prove the membership of the corresponding decision problems in the class NP and coNP.

引用

页码：87 / 99

页数：13

共 29 条

[1]

Bang-Jensen J., 1988, SIAM J DISCR MATH, V1, P281

[2] THE EFFECT OF 2 CYCLES ON THE COMPLEXITY OF COLOURINGS BY DIRECTED-GRAPHS [J].

BANGJENSEN, J ;

HELL, P .

DISCRETE APPLIED MATHEMATICS, 1990, 26 (01) :1-23

[3]

BANGJENSEN J, IN PRESS DISCRETE MA

[4]

BANGJENSEN J, UNPUB HEREDITARILY H

[5] ON THE CHROMATIC NUMBER OF THE PRODUCT OF GRAPHS [J].

DUFFUS, D ;

SANDS, B ;

WOODROW, RE .

JOURNAL OF GRAPH THEORY, 1985, 9 (04) :487-495

[6]

ELZAHAR H, 1908, COMBINATORICA, V5, P121

[7]

GUTJAHR W, IN PRESS J GRAPH THE

[8]

HAGGKVIST R, UNPUB MOTE UNIVERSAL

[9]

HEDETNIEMI ST, 1966, 0310544T U MICH TECH

[10] ON THE COMPLEXITY OF H-COLORING [J].

HELL, P ;

NESETRIL, J .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1990, 48 (01) :92-110

← 1 2 3 →