{"entities":{"Q2373444":{"pageid":2384187,"ns":120,"title":"Item:Q2373444","lastrevid":55926955,"modified":"2026-02-21T05:36:35Z","type":"item","id":"Q2373444","labels":{"en":{"language":"en","value":"On the density of trigraph homomorphisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5172587"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$EAB1482A-3E6D-4F92-92FC-1C9F129A25A3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"53cf44c6c8d257e8bf6451107afa6bdc455557c2","datavalue":{"value":{"text":"On the density of trigraph homomorphisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2373444$9229507E-1CD2-4AA5-BCA7-1458C892A817","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2c4d8add714a72ff091e97581223235f303dad84","datavalue":{"value":"1120.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$7C4CBBA9-99BA-42B8-AE43-1542DBF6C26E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$7B0D4D05-0FC5-4C0A-82AE-F1B8FEB943B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$B131A7F7-B827-4AD5-99E2-0DFF0A1A982C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$F3546B51-AE37-42D8-9EAC-B16B07F98782","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"227f49044efd7c327d9fee9eb29461e125a6d477","datavalue":{"value":{"time":"+2007-07-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2373444$9963907A-C88E-4343-B6BB-D62E56244A08","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"21e4634085393029597756074fdba57dde7ecf4d","datavalue":{"value":"A trigraph \\(G\\) consists of a finite set \\(V(G)\\) of vertices, and two (possibly intersecting) edge sets \\(E_1(G)\\), \\(E_2(G)\\) on \\(V(G)\\), such that \\(E_1(G)\\cup E_2(G)\\) contains all unordered pairs of (possibly equal) vertices. Let \\(G\\) and \\(H\\) be any trigraphs. A homomorphism \\(f\\) of \\(G\\) to \\(H\\) is a mapping of \\(V(G)\\) to \\(V(H)\\) such that \\(uv\\in E_i(G)\\) implies \\(f(u)f(v)\\in E_i(H)\\) (\\(i=1,2\\)). \\(G<H\\) means that there exists a homomorphism of \\(G\\) to \\(H\\), but not of \\(H\\) to \\(G\\); if \\(G<H\\) but there exists no \\(K\\) such that \\(G<K<H\\), \\(G<H\\) is called a gap.  From the authors' abstract: ``An order is dense if \\(A<B\\) implies \\(A<C<B\\) for some \\(C\\). The homomorphism order of (nontrivial) graphs is known to be dense. Homomorphisms of trigraphs extend homomorphisms of graphs'' [cf. \\textit{P. Hell} and \\textit{J. Ne\u0161et\u0159il}, Graphs and homomorphisms. Oxford University Press (2004; Zbl 1062.05139)], ``and model many partitions of interest in the study of perfect graphs.''   Two trigraphs are homomorphically equivalent if each admits a homomorphism to the other. A trigraph is a core if it is not homomorphically equivalent to any proper subtrigraph. A digon (respectively diloop) of \\(G\\) is a pair \\(u,v\\) of distinct (respectively identical) vertices such that \\(uv\\in E_1(G)\\cap E_2(G)\\); \\(G^*\\) is the subtrigraph induced by all vertices incident to digons.   Theorem 1. Suppose \\(G\\) and \\(H\\) are cores without diloops such that \\(G<H\\). If (1) \\(G\\) is a subtrigraph of \\(H\\) with \\(G^*=H^*\\); (2) every homomorphism of \\(G\\) to \\(H\\) is injective; and (3) the core of each proper subtrigraph of \\(H\\) which contains \\(G\\) is equal to \\(G\\), then \\(G<H\\) is a gap. Otherwise there exists a trigraph \\(K\\) with \\(G<K<H\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$E7CEE23F-E586-4CCE-8CBB-3A1F67B1AB9E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$EE5D213E-A04D-402A-8FC1-F20E2B0C25F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$02B8BA06-FE87-4B62-8B3A-429E3EF7AC15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$CD661A8C-C793-418A-B019-7E6F727193D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b42daad50918af7b1dd3a39d56f83fd36eb2116","datavalue":{"value":"5172587","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$CE646E77-E72B-4A0E-AB9C-559FAEC8DFC1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c155032f75c1637f8c61a0f5085d0d7fbca28010","datavalue":{"value":"trigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$1C934B48-7F52-41CC-80E7-F5ABEE08DFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$9B7454E3-F9D7-4F9E-8CD6-D51D9C249701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$654082FF-258A-479A-896C-1554A6AA403F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1adf8412449f81c61ade5704be1ae1ddf127dedd","datavalue":{"value":"gap","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$A7B9FF03-E1F5-4BB3-8CE3-825B74CFE423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2373444$1B92D63C-EC2A-4B4E-A0F6-7832640CA7FD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$0E5C6E90-88E1-4CD2-9F6B-4D9BA5E0EFFF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$F17B1A3F-34DA-4B51-995B-71C653162575","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"363dac9d6cf3db3c324ffdc0d82375ed8870d0c6","datavalue":{"value":"https://doi.org/10.1007/s00373-007-0712-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q2373444$15D7B0E9-798C-4FDF-AAF7-3E918038D62A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b9451278d59707914d4ba781b537cf119cbd481d","datavalue":{"value":"W1964336276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$A160CF9A-250E-4FFF-B277-43EBF649AF8F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$C519759D-963D-4038-A111-6F201AAAD28D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20e0b8b69bb74bc107c5a48305e78f34c64cd1d","datavalue":{"value":{"entity-type":"item","numeric-id":2494439,"id":"Q2494439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$717A9177-8CA0-4E8F-B2AD-A25656D8DF04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb824d887f98dd74ca6f1faa806c22f8d63b3d0e","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$FE01A3B5-7DA1-4CC6-84E6-7C0EDFD10B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b213c52a222d7efa3932cc69bfa23b3c133ebca0","datavalue":{"value":{"entity-type":"item","numeric-id":4521527,"id":"Q4521527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$397AE25A-3250-499C-9D8F-4E7D64BF89E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1478288fbfb8ca77d6855c6c3ca4dc8072bc6c49","datavalue":{"value":{"entity-type":"item","numeric-id":4443101,"id":"Q4443101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$BC605370-ED6B-44C7-8601-753AE7F1C2AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$79AAEB01-65FC-4203-8872-03938EB5DB8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22e517e30dc7b9af1670e9830d78d776d9a55e8e","datavalue":{"value":{"entity-type":"item","numeric-id":1215638,"id":"Q1215638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$3ADF90A1-7A39-47BB-8AA0-79289EF9B525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15f0d5d06eb8f30a0d71ed29f48211a4f9dca39","datavalue":{"value":{"entity-type":"item","numeric-id":1850486,"id":"Q1850486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$D8C67DE3-1260-4BEF-886E-F3DAEE20BC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dacc118959ac4406901793fdc048b61fa833ad70","datavalue":{"value":{"entity-type":"item","numeric-id":3208855,"id":"Q3208855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2373444$F5E4F440-E7DF-42B1-98D2-2230D4D12474","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"41802059f1e46264463aa13ebd1c6bf6fcc1e108","datavalue":{"value":"10.1007/S00373-007-0712-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2373444$9DC6E2DD-E4CE-4593-BD19-26BFB563925D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9aca34536d9581b074aa9d906f56f0798d815038","datavalue":{"value":{"entity-type":"item","numeric-id":2151176,"id":"Q2151176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"699ebf7280fd1b819cb34e5743421b58691aa8b3","datavalue":{"value":{"amount":"+0.865817","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$643B0F15-2B02-49FC-920D-55CB505EF492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3e5f154617f43becbf82aa568f0289299a9f339","datavalue":{"value":{"entity-type":"item","numeric-id":4242473,"id":"Q4242473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99d9325e08baab56495e11822523ed59637d59cf","datavalue":{"value":{"amount":"+0.85640824","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$A14D6B4A-7C56-4946-BE1C-636BD6C1533B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67dbcb86bda844afd0197a2603609b7c8eddf72c","datavalue":{"value":{"entity-type":"item","numeric-id":860407,"id":"Q860407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f9c1e48be799f850a3f3611802e2be019bb41f","datavalue":{"value":{"amount":"+0.85553896","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$41CC98AB-15DA-40DC-89FB-3B6EF6B87859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ce8f1d9c4fd43074717a0789cb5a50de5e15103","datavalue":{"value":{"entity-type":"item","numeric-id":4256688,"id":"Q4256688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bbb32fa749349b0177a8f246f6f58c7ad36cadca","datavalue":{"value":{"amount":"+0.85540235","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$B82511B5-FF44-4DD1-B37E-A39BF44F9E17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6726c01da33f8da6cff625f9eed5a8624f221325","datavalue":{"value":{"entity-type":"item","numeric-id":3527546,"id":"Q3527546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e56ebbbd910fd2b9918151da9cf44834db08b41e","datavalue":{"value":{"amount":"+0.85364854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$4B907121-C455-4CF8-BECF-5CF9A83B0C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"badb27f4b37f480c5b32f9f0f01a0500f24662f5","datavalue":{"value":{"entity-type":"item","numeric-id":2229160,"id":"Q2229160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92c7e123331d32eeb4a566c2131ee125560733ea","datavalue":{"value":{"amount":"+0.8511623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$0ECB643E-613E-43F8-A3FF-88FD16BA82FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a2ce22561089f96fef343732e09d656ee9a1b43","datavalue":{"value":{"entity-type":"item","numeric-id":896067,"id":"Q896067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3afa2c99a315c183d16735ceb01d2da57f84ffff","datavalue":{"value":{"amount":"+0.8510084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$46B31456-FD6D-497B-A70C-597879BECE51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6bf712e489bb151d4d856f0ff914e7c22c030e8f","datavalue":{"value":{"entity-type":"item","numeric-id":3318798,"id":"Q3318798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"688370eeb0147d601555ea2fff45290f0890d27e","datavalue":{"value":{"amount":"+0.8501481","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$591556D1-943E-4C44-B8FA-D5B559C73AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26e739bed8386b70cb830b2098ccf4604da0ac72","datavalue":{"value":{"entity-type":"item","numeric-id":1863057,"id":"Q1863057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cf09000947e8121ca35aec788b68cc8156eec37","datavalue":{"value":{"amount":"+0.8483001","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2373444$3B9BB16F-9E6F-4D07-AA28-68F607FB68E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2373444","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2373444"}}}}}