×

On finite maximal antichains in the homomorphism order. (English) Zbl 1341.05167

Márquez, Alberto (ed.) et al., Proceedings of the 4th European conference on combinatorics, graph theory and applications, EuroComb’07, Seville, Spain, September 11–15, 2007. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 29, 389-396 (2007).
Summary: We show that for structures with at most two relations all finite maximal antichains in the homomorphism order correspond to finite homomorphism dualities. We also show that most finite maximal antichains in this order split.
For the entire collection see [Zbl 1137.05002].

MSC:

05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Erdős, P.; Hajnal, A., On chromatic number of graphs and set-systems, Acta Math. Hungar., 17, 61-99 (1966) · Zbl 0151.33701
[2] Erdős, P.L. and L. Soukup, How to split antichains in infinite posets; Erdős, P.L. and L. Soukup, How to split antichains in infinite posets · Zbl 1136.06002
[3] Foniok, J.; Nešetřil, J.; Tardif, C., Generalised dualities and finite maximal antichains, (Fomin, F. V., Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, (Proceedings of WG 2006). Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, (Proceedings of WG 2006), Lecture Notes in Comput. Sci., 4271 (2006)), 27-36 · Zbl 1167.05319
[4] Foniok, J., J. Nešetřil and C. Tardif, Generalised dualities and maximal finite antichains in the homomorphism order of relational structures; Foniok, J., J. Nešetřil and C. Tardif, Generalised dualities and maximal finite antichains in the homomorphism order of relational structures · Zbl 1147.05037
[5] Hell, P.; Nešetřil, J., Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and Its Applications, 28 (2004), Oxford University Press · Zbl 1062.05139
[6] Hubička, J.; Nešetřil, J., Finite paths are universal, Order, 22, 21-40 (2005) · Zbl 1092.06002
[7] Nešetřil, J.; Rödl, V., Chromatically optimal rigid graphs, J. Combin. Theory Ser. B, 46, 133-141 (1989) · Zbl 0677.05031
[8] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterising gaps and good characterisations), J. Combin. Theory Ser. B, 80, 80-97 (2000) · Zbl 1024.05078
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.