{"entities":{"Q1881691":{"pageid":1892433,"ns":120,"title":"Item:Q1881691","lastrevid":57602364,"modified":"2026-03-31T14:08:41Z","type":"item","id":"Q1881691","labels":{"en":{"language":"en","value":"Box complexes, neighborhood complexes, and the chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2107888"}},"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":"Q1881691$1497DBDD-0B63-4581-856D-37971FE80B72","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ccb8684160eea035de26a55b3b0b01719f9f3680","datavalue":{"value":{"text":"Box complexes, neighborhood complexes, and the chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1881691$7A474550-64BA-4355-B62C-AE3BA0B03BED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0edbc3ee1cb5ac094b3884de06f1d3abe9519ce9","datavalue":{"value":"1060.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$BA299580-9458-49B6-8896-AE4E37D680AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"642997d06e4e203766bb8f65cdb9aa41dc1e5d44","datavalue":{"value":{"entity-type":"item","numeric-id":834613,"id":"Q834613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$D0161EA8-52F3-4A72-8CD1-B8510C8BCCAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e0a661cae43bede8663db3faa6a62f1b9eb02fcd","datavalue":{"value":{"entity-type":"item","numeric-id":1881689,"id":"Q1881689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$DCACB4C7-A55C-4B31-A179-779EE9A68313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb43a1fb78475cceb8521592842925d3e3cd2dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1881690,"id":"Q1881690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$3FF05680-3727-4F71-A3B5-5D6CF74F07D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a80841153b809e031968e5f258762e028b8ddfdb","datavalue":{"value":{"entity-type":"item","numeric-id":393728,"id":"Q393728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$EC8C4F58-1A5D-4B9B-9CBD-F93A29F6C4F2","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$DF5BE21B-2AEA-4844-B3B0-3DCC0DAD81DB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6608e2cb89851be6f08755fc1feb8d6ac1df11a0","datavalue":{"value":{"time":"+2004-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1881691$D63DA397-B55B-48DC-B703-323D68AAE07C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"948494e0f7a8cabcc786d950b7a5fe0381eef73f","datavalue":{"value":"https://arxiv.org/abs/math/0310339","type":"string"},"datatype":"url"},"type":"statement","id":"Q1881691$C0CC45B6-802B-4A21-B1E3-309F82544613","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0653b15f4124e852f3b1779ff5724f7882921dea","datavalue":{"value":"The connectivity of certain simplicial complexes (neighborhood complex, box complexes) associated with a graph yields lower bounds for the chromatic number. Since L. Lov\u00e1sz' proof of the Kneser conjecture [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] this insight has been explored in a number of directions; for a recent survey see \\textit{J. Matou\u0161ek} and the reviewer [Topological lower bounds for the chromatic number: a hierarchy, Jahresber. Dtsch. Math.-Ver. 106, 71--90 (2004; Zbl 1063.05047)].  It is known that the topological lower bounds for the chromatic number are weak for graphs with few complete bipartite subgraphs. In particular, for \\(C_4\\)-free graphs the lower bound will be trivial. This is extended in this paper to graphs without a \\(K_{\\ell,m}\\) subgraphs: For these the index of the box complex is at most \\(\\ell+m-3\\), so the lower bound for the chromatic number is no better than \\(\\ell+m-1\\). This is derived as part of a detailed study of some box complexes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1881691$26D2D23C-173B-4733-9154-0479FAC5E680","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$95306E34-9087-43B3-BB3C-D0EBEECF73C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$8A01CCA7-D1EE-41AF-83C5-D8E65F1B6851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c20816b15de71eb2afe3565caf954727a3a64001","datavalue":{"value":"55P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$FB9CAC20-D64E-43D6-B52A-060183518F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8d5ada37b1398532b96572a582dac34014ee17ec","datavalue":{"value":"57M15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$458C778B-7619-4EA9-B0E0-A9FC2766F605","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05d6215d8a9b9ffea10546c49ee9e816b5343585","datavalue":{"value":"2107888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$FE3E4037-DF42-45CE-B3F2-147A35D42C27","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1881691$11689D3C-1FA7-4576-A790-D210F1BCF525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1853d5e16f8b63fccd584cb907fabdbc6c4240b2","datavalue":{"value":"Kneser conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1881691$CDF0CD68-5D98-44FF-BB81-20B789A0112C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f35f5389734943a96bfa0f9462689ac5470515fd","datavalue":{"value":"box complexes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1881691$0D9E393F-88D8-4DDB-91B4-9A2B349BECDE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2a414f06c82d770f131a5979daa1aa099bf5faff","datavalue":{"value":{"entity-type":"item","numeric-id":189313,"id":"Q189313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$092C7367-41E5-4AB8-BE1C-B4643C443F8B","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":"Q1881691$381E7C47-3CF8-4771-A345-EC53D017B0C4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"02887dac6d97a461f710a549f6ab7656d757b37a","datavalue":{"value":"W2097771028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$5CFFBA59-8C5F-4A8E-A74C-E1759D94F17F","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":"Q1881691$ECFF62B5-6A67-4360-A305-EFC44D879C9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f346f6935eab8f7bfd8c5b35d3ff010b785bc3a1","datavalue":{"value":{"entity-type":"item","numeric-id":4860774,"id":"Q4860774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$95208A34-D2A8-4FC3-9D35-CA902193088B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc5874427d4b1bb98d72cd3d9e06816eb88256f","datavalue":{"value":{"entity-type":"item","numeric-id":598461,"id":"Q598461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$6ECB808E-7D6E-4E76-8EB7-D06EDC6DCB85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23313ba0f3dbe073d2c9de97d2d4798b84972dd1","datavalue":{"value":{"entity-type":"item","numeric-id":4015877,"id":"Q4015877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$ED272FF5-7497-4ED6-90FE-BAA9970F5725","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":"Q1881691$A19B9536-E2A9-4370-B830-69677EA14306","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8b656de080ff5b24898858b58fde36475098a8a","datavalue":{"value":{"entity-type":"item","numeric-id":5917516,"id":"Q5917516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$B57E57F7-A4E9-42EA-A991-5E089DF585B8","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":"Q1881691$3408883D-9E3D-4AEF-950D-19FD3E72771B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ce3ef18a5342adb26400dfa87bdf90970afb7f1","datavalue":{"value":{"entity-type":"item","numeric-id":750443,"id":"Q750443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$523E9B24-81C8-416A-AB67-F7B923051DB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37ed236915ccb1233f4787e6cd0c1006c86717b8","datavalue":{"value":{"entity-type":"item","numeric-id":1838501,"id":"Q1838501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1881691$FC1AEC52-169C-4092-A99D-C9D3C028AB09","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"425b617c686213a8a7b5676edce4e04a5b3445bb","datavalue":{"value":"10.1016/J.JCTA.2004.06.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1881691$78039942-D8CA-4398-B203-B11C84982ABE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"398ff5385c6ed1d74f156c1bb8a59fff10a5be3e","datavalue":{"value":{"entity-type":"item","numeric-id":1689736,"id":"Q1689736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"492bd1956e226257fa332172d0f49573e43f7863","datavalue":{"value":{"amount":"+0.8855813","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":"Q1881691$A5F3F81B-C77A-4270-AE7F-0666ED29861D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83dbcd5f4158d2e4a8b02f10b367a256ae859a77","datavalue":{"value":{"entity-type":"item","numeric-id":1032693,"id":"Q1032693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"551727766ae41256a067aac4621c82fa0813ff55","datavalue":{"value":{"amount":"+0.8795674","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":"Q1881691$B24F9FAE-B4EF-45D4-9F0E-05B9F7021218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1803032f80abd94024330213d1359cecb922069","datavalue":{"value":{"entity-type":"item","numeric-id":722323,"id":"Q722323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8bbd52ff5f4cf8e0975558ced41b24d9a0664cc","datavalue":{"value":{"amount":"+0.87336993","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":"Q1881691$A39558AC-EF57-4744-8FBD-AA0D6AC12BB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e417ff1d597eec0963c8f45ac6c0c88a6c1d796","datavalue":{"value":{"entity-type":"item","numeric-id":4203042,"id":"Q4203042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd157957e4e450037512e037b611eb196495e22e","datavalue":{"value":{"amount":"+0.87221473","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":"Q1881691$5ED8CA1B-F48C-4DB9-9375-5BC0DD45DD0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e0567fbb77177afa115e97aad4e64bf7c87dc1e","datavalue":{"value":{"entity-type":"item","numeric-id":5432047,"id":"Q5432047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"40af7b896c2715629345cb293b440919b274947c","datavalue":{"value":{"amount":"+0.8717621","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":"Q1881691$30F76BDC-AEDE-4830-91C9-B9DF86CA30A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77bdab2a89946e123fcfeab64340170993893d28","datavalue":{"value":{"entity-type":"item","numeric-id":1398200,"id":"Q1398200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9a59b04dc8b09d16fb86c7face2cca9c90ce840","datavalue":{"value":{"amount":"+0.87121713","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":"Q1881691$8D4DC5BB-9E66-4F8B-B1B2-37423F7147F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51b195f651dbc40047a41686582b7326025d185e","datavalue":{"value":{"entity-type":"item","numeric-id":5688995,"id":"Q5688995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d4d8bc9f2703dbb9fa12edf52a14950e5db525f7","datavalue":{"value":{"amount":"+0.8694711","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":"Q1881691$D07CCE6A-9183-4C75-B0A4-325E3E941941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a766b00d60a66bfd48a47e1103f979d762323f46","datavalue":{"value":{"entity-type":"item","numeric-id":966142,"id":"Q966142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bea65786abf4f256610d1c01a095067f1b6447fe","datavalue":{"value":{"amount":"+0.8653474","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":"Q1881691$EB5CFE18-563B-4489-9EE5-CDFFCF7CEEF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e3695d3bec62e671285a4dd2726dcb78770daa8","datavalue":{"value":{"entity-type":"item","numeric-id":4779337,"id":"Q4779337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64e3eaffafb9eaf2a368ad25a7c23b09dedea228","datavalue":{"value":{"amount":"+0.86423796","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":"Q1881691$3B28C70C-91B6-4E97-8C28-91D54FDC1AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea7928bb6ac5a22cb4146ad0b0b32f9ee6c8f7eb","datavalue":{"value":{"entity-type":"item","numeric-id":784756,"id":"Q784756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43f20d972106f111041f652a0c3eea70610e1e9c","datavalue":{"value":{"amount":"+0.8622906","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":"Q1881691$C8ABD081-5802-4324-BFA3-CB2ECB281168","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1881691","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1881691"}}}}}