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. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 23 October 2019

THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS

THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS

Chapter:
(p.81) 3 THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS
Source:
Graphs and Homomorphisms
Author(s):

Pavol Hell

Jaroslav Nešetřil

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

This chapter considers the order homomorphisms induce on the set of all cores; this order is rich enough to represent all countable partial orders. Antichains in the homomorphism order are discussed, which are collections of incomparable graphs (graphs without homomorphisms between any two of them). Of particular interest are finite maximal antichains, and their structure turns out to be surprisingly revealing. Graphs only have trivial finite maximal antichains, while digraphs have many such antichains of all possible sizes, arising from duality relationships. This chapter also contains the (probabilistic) proof of the Sparse Incomparability Lemma, of the fact that asymptotically almost all graphs on $n$ vertices are cores, and of the fact that the number of incomparable graphs on $n$ vertices differs little (asymptotically) from the total number of non-isomorphic graphs on $n$ vertices. The density of the homomorphism order is related to duality, revealing an unexpected connection between these two seemingly unrelated concepts. Finally, it is shown that one can gain interesting insights into many traditional graph topics, such as Hadwiger’s conjecture, when interpreting them as statements about the homomorphism order.

Keywords:   partial order, homomorphism order, homomorphic equivalence, core, chains, antichains, duality, density, incomparability, Hadwiger’s Conjecture

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 .