Jump to ContentJump to Main Navigation

Graphs and Homomorphisms

Pavol Hell and Jaroslav Nesetril

Abstract

Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. This text is devoted entirely to the subject, bringing together the highlights of the theory and its many applications. It looks at areas such as graph reconstruction, products, fractional and circular colourings, and constraint satisfaction problems, and has applications in complexity theory, artificial intelligence, telecommunications, and statistical physics. It has a wide focus on algebraic, combinatorial, and algorithmic aspects of graph homomorp ... More

Keywords: digraphs, partial orders, reconstruction, colourings, fractional colourings, products, algebraic combinatorics, structures, complexity theory, constraint satisfaction

Bibliographic Information

Print publication date: 2004 Print ISBN-13: 9780198528173
Published to Oxford Scholarship Online: September 2007 DOI:10.1093/acprof:oso/9780198528173.001.0001

Authors

Affiliations are at time of print publication.

Pavol Hell, author
Simon Fraser University, Burnaby, B.C., Canada

Jaroslav Nesetril, author
Charles University, Prague, The Czech Republic