List homomorphisms and circular arc graphs
type: Item
instance of: scholarly article
title: List homomorphisms and circular arc graphs
zbMATH Open document ID: 0985.05048
author: Tomás Feder
author: Huang Jing
author: Pavol Hell
published in: Combinatorica
publication date: 2000-05-14T00:00:00Z
review text: The list homomorphism problem for a graph \(H\) has as input a graph \(G\) and lists \(L(v)\subseteq V(H)\) for the vertices \(v\in V(G)\). The output is a homomorphism \(f:G\to H\) with \(f(v)\in L(v)\) for every \(v\in V(G)\). It is shown that if \(H\) is loopless then this problem is polynomially solvable if \(\overline{H}\) is a circular arc graph of clique covering number 2, otherwise it is NP-complete. A new characterization is given for the former case.
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1446786
zbMATH Keywords: graph homomorphisms
zbMATH Keywords: list chromatic number
reviewed by: Péter Komjáth
MaRDI profile type: Publication
full work available at URL: s004939970003
OpenAlex ID: W2033470072
DOI: 10.1007/S004939970003
description: scientific article; zbMATH DE number 1446786