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 (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 31 October 2020



Graphs and Homomorphisms

Pavol Hell

Jaroslav Nešetřil

Oxford University Press

This chapter focuses on certain basic constructions that occur frequently in the rest of the book, emphasizing the product and the retract, but also considering other constructs. These include the shift graph, the exponential graph, and the Lovász vector. Taken together, such constructions are the common thread and the leitmotiv of this book. The highlights of the sections on products include a linear algebra-based lower bound on the dimension of a graph; a stronger version of the edge reconstruction result from this chapter; a discussion of cancellation and unique factorization properties; a construction of graphs with arbitrarily high odd girth and chromatic number; an exploration of the Product Conjecture; and an elementary proof of the multiplicativity of oriented cycles of prime power length. The sections on retracts contain the proof that an isometric tree and a shortest cycle is always a retract of a reflexive graph; a similar result holds for shortest odd cycles in irreflexive nearly bipartite graphs. Absolute reflexive retracts are characterized in several different ways, including characterizations in terms of majority functions, the variety of paths, and the Helly property (or the absence of holes). A reflexive graph is shown to admit a winning strategy for the cop in the game of cops and robbers, if and only if it is dismantlable, and dismantlable graphs are related to absolute reflexive retracts. Finally, median graphs are introduced and related to retracts of hypercubes. An application of median graphs and retractions is given in a resource location problem.

Keywords:   reconstruction, cancellation, unique factorization, odd girth, chromatic number, multiplicativity, absolute retract, majority function, Helly property, dismantlability

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 .