[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.
Disciplines :
Mathematics
Author, co-author :
Lehtonen, Erkko
SCHÖLZEL, Karsten ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit
Language :
English
Title :
Intervals of the homomorphism order of graphs have infinite width
