The Library
Dichotomy for tree-structured trigraph list homomorphism problems
Tools
Feder, Tomás, Hell, Pavol, Schell, David G. and Stacho, Juraj (2011) Dichotomy for tree-structured trigraph list homomorphism problems. Discrete Applied Mathematics, Vol.159 (No.12). pp. 1217-1224. doi:10.1016/j.dam.2011.04.005 ISSN 0166-218X.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.dam.2011.04.005
Abstract
Trigraph list homomorphism problems, also known as list matrix partition problems, generalize graph list colouring and digraph list homomorphism problems. While digraph list homomorphism problems enjoy a dichotomy (each problem is -complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems, and in the few cases where dichotomy has been proved, for small trigraphs, the progress has been slow.
In this paper, we prove dichotomy for trigraph list homomorphism problems where the underlying graph of the trigraph is a tree. In fact, we show that for these trigraphs the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. The result can be extended to a larger class of trigraphs, and we illustrate the extension on trigraph cycles.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
Journal or Publication Title: | Discrete Applied Mathematics | ||||
Publisher: | Elsevier Science Ltd. | ||||
ISSN: | 0166-218X | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Volume: | Vol.159 | ||||
Number: | No.12 | ||||
Page Range: | pp. 1217-1224 | ||||
DOI: | 10.1016/j.dam.2011.04.005 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |