Jump to ContentJump to Main Navigation
Graphs and Homomorphisms$
Users without a subscription are not able to see the full content.

Pavol Hell and Jaroslav Nesetril

Print publication date: 2004

Print ISBN-13: 9780198528173

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198528173.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (www.oxfordscholarship.com). (c) Copyright Oxford University Press, 2019. All Rights Reserved. Under the terms of the licence agreement, an individual user may print out a PDF of a single chapter of a monograph in OSO for personal use (for details see www.oxfordscholarship.com/page/privacy-policy).date: 17 June 2019

TESTING FOR THE EXISTENCE OF HOMOMORPHISMS

TESTING FOR THE EXISTENCE OF HOMOMORPHISMS

Chapter:
(p.142) 5 TESTING FOR THE EXISTENCE OF HOMOMORPHISMS
Source:
Graphs and Homomorphisms
Author(s):

Pavol Hell

Jaroslav Nešetřil

Publisher:
Oxford University Press
DOI:10.1093/acprof:oso/9780198528173.003.0005

This chapter explores the algorithmic aspects of graph homomorphisms and of similar partition problems. The highlights include the dichotomy classification of graph homomorphisms to a fixed target graph $H$; a proof of the fact that dichotomy for digraph homomorphisms would imply dichotomy for all constraint satisfaction problems; a presentation of consistency-based algorithms; and associated dualities that seem to be applicable to all known polynomial cases of the digraph homomorphism problem. The role of polymorphisms in the design of polynomial algorithms is highlighted, and it is shown that graphs with the same set of polymorphisms define polynomially equivalent problems. The polymorphism known as the majority function is shown to yield a polynomial time homomorphism testing algorithm. The dichotomy classification of list homomorphism problems for reflexive graphs is presented. List matrix partition problems are posed in the language of trigraph homomorphisms, and the richness of the associated algorithms is illustrated on the case of clique cutsets and generalized split graphs.

Keywords:   $H$-colouring problem, NP-completeness, polynomial algorithm, dichotomy, constraint satisfaction problem, polymorphism, list homomorphisms, matrix partitions, trigraphs, split graph

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .