Reference : Intervals of the homomorphism order of graphs have infinite width
E-prints/Working papers : First made available on ORBilu
Physical, chemical, mathematical & earth Sciences : Mathematics
Intervals of the homomorphism order of graphs have infinite width
Lehtonen, Erkko []
Schölzel, Karsten mailto [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
[en] graph homomorphism ; density ; antichain
[en] The homomorphism order of graphs is known to be dense with a single exception. We strengthen this result by showing that, with this single exception, the interval between any two distinct comparable graphs includes an infinite antichain. Moreover, every antichain included in such an interval can be extended into an infinite one within that interval.

File(s) associated to this reference

Fulltext file(s):

Limited access
Density.pdfAuthor preprint204.81 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.