[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 :
Mathématiques
Auteur, co-auteur :
Lehtonen, Erkko
SCHÖLZEL, Karsten ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit
Langue du document :
Anglais
Titre :
Intervals of the homomorphism order of graphs have infinite width
