PRODUCTS AND RETRACTS
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.
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.
If you think you should have access to this title, please contact your librarian.