{"entities":{"Q2382336":{"pageid":2393079,"ns":120,"title":"Item:Q2382336","lastrevid":57881727,"modified":"2026-04-02T22:37:11Z","type":"item","id":"Q2382336","labels":{"en":{"language":"en","value":"Complexes of graph homomorphisms"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5198510"}},"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":"Q2382336$514A4B91-6A0D-41DF-A815-A782F22703D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"edf3dd82e28b1c1e1ec0b84b5b5cf9b1d2225608","datavalue":{"value":{"text":"Complexes of graph homomorphisms","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2382336$518CE71A-7735-4890-9EB2-3A34F5B9A110","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a56040ab7d3e566a9a68c44e7af7b35b1b251286","datavalue":{"value":"1205.52009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$BFF596AB-0E42-4874-BFF0-8FD3FD1E697B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1fad7d4a5ebff5ef91b589b7ed6d409cb567d420","datavalue":{"value":"10.1007/BF02771988","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$CAE7CF14-CFC4-4F88-9416-6E338813B8DB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa10dd5ff86b90148599be0dcd01111d7da8ecad","datavalue":{"value":{"entity-type":"item","numeric-id":1376052,"id":"Q1376052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$5AE4DF5A-9BFC-4CE5-B961-AD15440348F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fbe52a955fe87ebf7724ee2cb9164de8d0f8099b","datavalue":{"value":{"entity-type":"item","numeric-id":215085,"id":"Q215085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$08C1F551-E994-42F0-87C3-1DB9F75970EE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$D45B3CE1-E98B-4E79-9D85-7777CAF4329E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a1c6d1eb5a1881a1c15c479f8c9d6be5d5505633","datavalue":{"value":{"time":"+2007-10-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2382336$A36C82BE-FD8F-4746-9C21-701AC4CCBCD9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"245bc331b9339948e6acbda6a4e9f2fa1ff9e887","datavalue":{"value":"https://arxiv.org/abs/math/0310056","type":"string"},"datatype":"url"},"type":"statement","id":"Q2382336$739B2659-CA9D-44AB-8D46-C76DCE42694A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eb8ec50b40ccc618b1d032e4059c0f5cb5778572","datavalue":{"value":"For any two graphs \\(G\\) and \\(H\\) there is a polyhedral complex \\({\\Hom}(G,H)\\), the \\textit{Hom-complex} of \\(G\\) and \\(H\\), whose vertices are the graph homomorphisms from \\(G\\) to \\(H\\). Especially interesting are the complexes \\({\\Hom}(G,K_n)\\) where \\(K_n\\) is the complete graph on \\(n\\) nodes. This complex is non-empty if and only if \\(G\\) admits a proper coloring of its nodes with \\(n\\) colors.  In the paper under review the authors prove a number of combinatorial and topological results about Hom-complexes. In particular, they show that \\({\\Hom}(K_2,G)\\) is homotopy equivalent to the neighborhood complex of \\(G\\). The degree of connectedness of the latter is known to form an obstruction to the colorability of \\(G\\) from \\textit{L. Lov\u00e1sz}' solution of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)].  Moreover, it is proved that \\({\\Hom}(K_m,K_n)\\) is homotopy equivalent to a wedge of \\((n-m)\\)-dimensional spheres, and a recurrence relation is given for their number. Other results involve the computation of homotopy types of Hom-complexes from finite forests to complete graphs. The techniques developed in this paper were applied in the authors' proof [Ann. Math. (2) 165, No.~3, 965--1007 (2007; Zbl 1132.05019)] of a conjecture of Lov\u00e1sz.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382336$22118770-3EA5-42AE-BE2A-B85C3CBC960E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9208765f4f15600d78a268b03771f90a99abcc6b","datavalue":{"value":{"entity-type":"item","numeric-id":161115,"id":"Q161115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$4212D895-AA28-4892-839C-5218E59C0157","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd73672ce3d9f471e9d23297d964a3c571416abc","datavalue":{"value":"52B70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$D3D97C1F-E4DF-4385-958F-B8C1A020DF30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$474D6F9A-DAA2-4761-BCE4-7BF7CCF87246","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"45a7869a20e2d427cc414582fb6c89072f9fb3f3","datavalue":{"value":"5198510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$26A7347F-0A8C-478F-A6D5-04C3C7ACB7C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db52bd8505c166911b68b4a8bdb96e742c059ccd","datavalue":{"value":"Hom-complex","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382336$25DF8AAA-FD0C-437C-B8F1-B1AD00E9C45F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d260a30e3f791ee7d7a2a100ccc1d5cbac0b0b23","datavalue":{"value":"topological obstructions to graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382336$2BF6F19A-BB0D-4590-A500-D7A15932F57B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cb040557cfd12318d7485732bd264da10448c90","datavalue":{"value":"Quillen type results","type":"string"},"datatype":"string"},"type":"statement","id":"Q2382336$1FD0ACB4-E732-43F4-996A-3E128A8EB9CA","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":"Q2382336$9506F41C-5D0B-45DD-82DB-0ACC65B01235","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"206a687e585ae4987de04449b0298662542d9a57","datavalue":{"value":{"entity-type":"item","numeric-id":3743337,"id":"Q3743337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$FC60403C-9BE8-4A33-B787-523128F4F540","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2df2c1b8e4bb939c2d4921489a2088c549503d37","datavalue":{"value":{"entity-type":"item","numeric-id":1292680,"id":"Q1292680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$EB6E8CE8-E83B-4944-8B9F-CB85126AFA35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4817e95ce2bbba76c5bf2983b84286c611cbe949","datavalue":{"value":{"entity-type":"item","numeric-id":4680992,"id":"Q4680992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$20892ADB-4FBA-48CE-8FE2-41F9371F7B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1967d75efb946ba855c8315468d62db3c24ca59d","datavalue":{"value":{"entity-type":"item","numeric-id":3900673,"id":"Q3900673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$F52208C0-8998-4F12-B033-310CDBC3DB51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8f5d0749e63668e74a75eb5adf28f40df8e18fd","datavalue":{"value":{"entity-type":"item","numeric-id":4720067,"id":"Q4720067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$F231BA85-A471-4CB0-8355-7F7E51229A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b13af3971e6f7c652bbb28a3374a85b3dae7160a","datavalue":{"value":{"entity-type":"item","numeric-id":5694429,"id":"Q5694429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$9DC18DE4-72A2-4F2E-B9A9-F75AFF8AC7F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b30a6865b9a083fa5544cf9dab75dafdd99dee36","datavalue":{"value":{"entity-type":"item","numeric-id":1385240,"id":"Q1385240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$F086F774-AF55-452E-998F-2C03AD85B68A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2bbcea5ede7002d32a131fa3982fed8c0e2f246","datavalue":{"value":{"entity-type":"item","numeric-id":4955820,"id":"Q4955820"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$14A97BC5-9349-455B-92ED-A8DBF86C828F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61f34abda4ec6928e0b0f22ed177ff620e035271","datavalue":{"value":{"entity-type":"item","numeric-id":4817668,"id":"Q4817668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$56A1FE75-D71E-45F7-A121-F41B90B0400C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d1fa31901204946311777b983baf8bd026793d2","datavalue":{"value":{"entity-type":"item","numeric-id":3372106,"id":"Q3372106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$37338940-B5E3-4300-AFA1-46BA63E33A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b497f67016d886e8dca9fbf10fac6ad91307f10f","datavalue":{"value":{"entity-type":"item","numeric-id":5432047,"id":"Q5432047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$B7EF8436-4462-4192-8A76-0A7BD3CE7DFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c428f1852e95384416608cd782a84ad75e86d42b","datavalue":{"value":{"entity-type":"item","numeric-id":755592,"id":"Q755592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$BCAD7D6B-3B4F-4F96-BD54-399A3BA442EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cfce7cabaa7b2db6bb23de78169bce981ea8008","datavalue":{"value":{"entity-type":"item","numeric-id":1767268,"id":"Q1767268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$0510EEF3-ABAB-4455-8C85-351C19AAD184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f7caa6318d6b7d8b1e006d6217163dd1d34d0cd","datavalue":{"value":{"entity-type":"item","numeric-id":2368128,"id":"Q2368128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$36DF36B8-629E-4962-967A-31A216ABFC7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7208b18849b0782a96c2c03fc044dc3a03508e5c","datavalue":{"value":{"entity-type":"item","numeric-id":1087186,"id":"Q1087186"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2382336$3B831B42-5903-4C2D-A6AD-DAA117B096AB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a73e5f7a103ec64363f82382b2693770600ad1c5","datavalue":{"value":"W2001411993","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2382336$6E8F8C44-6771-490A-98A1-6C17FBC69EB4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf9b2c17bbca52e4ba1c69a40e7375148d80301d","datavalue":{"value":{"entity-type":"item","numeric-id":5694429,"id":"Q5694429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf747b5c0dbfb7477e46c38f83488d83ac036cd4","datavalue":{"value":{"amount":"+0.8721908926963806","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382336$83E21E30-32BC-4E09-A6A2-DAFF02C3B5A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82dc776f018f26d81a2641b333e5e73dc21405a3","datavalue":{"value":{"entity-type":"item","numeric-id":3106067,"id":"Q3106067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45b316d39fdc7785347484308fc16d6221c781ec","datavalue":{"value":{"amount":"+0.859595537185669","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382336$12320828-BAE0-40A9-AD62-2C279115272F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d006be92b1f339ef32b757f8cc87008ae7f5cdae","datavalue":{"value":{"entity-type":"item","numeric-id":3419958,"id":"Q3419958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3472d19664aeb62c97ff12b16e4cb96e07f9298e","datavalue":{"value":{"amount":"+0.8527818918228149","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382336$BD551F51-7BD3-445F-AC6E-F79B66392AD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c84a11d71145827d18a947d3e017aaf32980ddff","datavalue":{"value":{"entity-type":"item","numeric-id":2357231,"id":"Q2357231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c2fda8a05763bf73eb9f182e541fdefe3e3500c","datavalue":{"value":{"amount":"+0.8489317893981934","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382336$02DA258E-3F70-45CA-80E1-6769E3262832","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b23c1bc52ee5c2baecd1fce74d2fdc995f5ae1e","datavalue":{"value":{"entity-type":"item","numeric-id":987561,"id":"Q987561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0a9a57b5edcbf5f437b0468c5463d2c5a84ad81","datavalue":{"value":{"amount":"+0.8484821319580078","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2382336$56FCF7C2-67C5-43BE-8403-98CF4B8D9066","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2382336","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2382336"}}}}}