{"entities":{"Q1329806":{"pageid":1340556,"ns":120,"title":"Item:Q1329806","lastrevid":68843304,"modified":"2026-04-13T02:26:17Z","type":"item","id":"Q1329806","labels":{"en":{"language":"en","value":"Constructing colorings for diagrams"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 612432"}},"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":"Q1329806$6C039706-4ADC-4DF8-B0DE-1306B732A4B8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cee565b5a8fdcf5caa21870518b990eb466728b0","datavalue":{"value":{"text":"Constructing colorings for diagrams","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1329806$70103F05-2E04-4FE0-A5AE-A7D5F650BC3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a76c9e4229fe682775ea4d3e8e2a92bb8fc9da82","datavalue":{"value":"0805.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$80239292-D904-4930-B73A-7364B506442C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"94a3071edcd0ea2d88e41047b93d03db7dcb13f8","datavalue":{"value":"10.1016/0166-218X(94)90096-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$AF5411EA-348D-4FD5-AC9D-60B4A93A41E2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb43e4c4f1b169e3803b8b6726a3b03e15c78164","datavalue":{"value":{"entity-type":"item","numeric-id":170482,"id":"Q170482"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$6EBE9C25-541D-42F5-A985-A318E1186486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e89db102d8bcca1d9e21dab092378fca0af3b615","datavalue":{"value":{"entity-type":"item","numeric-id":666106,"id":"Q666106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$CE74414C-648D-4100-BB13-B1453CA03F8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8df8473580292261a411736bd6cfd3438c1bf27","datavalue":{"value":{"entity-type":"item","numeric-id":211630,"id":"Q211630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$BCB864CA-5C32-4F8B-A332-0CA9432CB316","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"360175f44a31d0aabada1dccaeea5239e64be551","datavalue":{"value":{"entity-type":"item","numeric-id":841167,"id":"Q841167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$D1A55FA3-7A7C-4313-BAC1-CE18B7411F37","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$5091D2E8-908A-409E-AA5E-FA18ED992110","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9dcb62c2b4917099426fc9f5c2e7993c2b745020","datavalue":{"value":{"time":"+1995-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1329806$6A3DB5BB-570B-4FC6-B5A5-4E6073448A7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ea88efc2047fc757172a273d7ace4ea1f74a51f3","datavalue":{"value":"An undirected graph \\(G=(V,E)\\) is a (Hasse)-diagram if there is a poset \\(P=(V,<)\\) and an orientation \\(\\vec E\\) of \\(E\\) such that \\((x,y) \\in \\vec E\\) iff \\(x<y\\) in \\(P\\) and there is no \\(z\\) with \\(x<z<y\\). One then writes \\(G=D_ P\\). \\textit{J. Ne\u0161et\u0159il} and \\textit{V. R\u00f6dl} [Order 3, 321- 330 (1987)] showed that calculating the chromatic number \\(\\chi\\) is NP- hard for diagrams. The authors give bounds for the chromatic number of an arbitrary diagram. Lattices and 2-dimensional posets can have diagrams of arbitrarily large chromatic number as shown by \\textit{B. Bollob\u00e1s} [Algebra Univers. 7, 313-314 (1977; Zbl 0374.06004)] and \\textit{I. K\u0159i\u017e} and \\textit{J. Ne\u0161et\u0159il} [Order 8, No. 1, 41-48 (1991; Zbl 0757.05053)], respectively. The authors construct a family of interval orders \\(I_ k\\) that are also \\(N\\)-free for which \\(\\chi (D_{I_ k}) = k\\). Individual bounds are determined for interval orders and for \\(N\\)-free orders.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$A7CCAA16-8E1B-4168-9D5E-574A71B5707D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$737995F6-2547-45B9-ACB2-638C17530945","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$44860899-4B13-4066-81D4-EB1C2160CEEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$B0181137-5BD7-4341-B207-9B21F8A079BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17a44832dadc03ef51f9feada062779f3c9c85da","datavalue":{"value":"612432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$EE3135B2-10FB-4937-83F2-46BDF9F4FC33","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245bb46b54951018ca725c73286f7f519e3b12ac","datavalue":{"value":"colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$945D721A-BA86-4691-A2B5-154314F4DD9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f801b7b85184e4eddf228cbd5e4be9de36123b58","datavalue":{"value":"\\(N\\)-free orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$B384539B-BF2F-4B3D-A8D6-6C1A0CF375C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762a112ef0429a3655234c3e246a242461dca9bf","datavalue":{"value":"poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$1C0AB31C-F383-486E-A0F7-3D25953A3BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$3EC24E2E-ACE6-42FF-851B-8F43B9845EAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$1F8578E4-BE7F-4C14-B0A8-45E22A2E3ADA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61e8e9f8f7d5b99330e59c1d6472f5f0dae2d8b9","datavalue":{"value":"diagrams","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$072E2E53-AD4E-4607-A4C0-7D49252CDC94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62d18420b0848a4c0300452d10ba1f75d74dc0e1","datavalue":{"value":"interval orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1329806$30BDF4FF-6BFC-410E-AFC4-907E33658754","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4160ba73cc613e2769e008ae8a9ce69c96d8603f","datavalue":{"value":{"entity-type":"item","numeric-id":207053,"id":"Q207053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$B70D205E-ECE6-48B2-A68B-AEB06256172C","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":"Q1329806$74ACB44F-EE00-4925-A309-FE852DA3BCE2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"52c7540760fe9ef3923a27be3c87c2aba62dfedc","datavalue":{"value":{"entity-type":"item","numeric-id":1149967,"id":"Q1149967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$11CF1E11-1415-4CD4-A3DF-27EFD7564A5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9602222e5a47f4cdffba25fcbf24545caa12e3c4","datavalue":{"value":{"entity-type":"item","numeric-id":1245243,"id":"Q1245243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$DF08B496-3978-47E9-8D8E-48BE8B652DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d03906c4e4edbec808b168a95f9d2b74581044dd","datavalue":{"value":{"entity-type":"item","numeric-id":4712020,"id":"Q4712020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$ED739E37-18B7-4317-86AD-615E4E48A092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"937cac11aec12eb2e346421f9803cc7c18c9db07","datavalue":{"value":{"entity-type":"item","numeric-id":787165,"id":"Q787165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$9B82E11B-9D34-4BD7-878B-C76C36DEA0EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8406bc96e7af3eadbb7276b92b44254fa600dbba","datavalue":{"value":{"entity-type":"item","numeric-id":2550401,"id":"Q2550401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$2F54175A-DCA0-45BD-AFBF-CE756987513F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b88560ad6d10ffb98ff92c42ec5911cea024165","datavalue":{"value":{"entity-type":"item","numeric-id":1182040,"id":"Q1182040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$84862961-530D-4135-A4FA-C352D75100B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7cbae1c1118a2e1a65c80b733f652572b93c30","datavalue":{"value":{"entity-type":"item","numeric-id":4918387,"id":"Q4918387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$6F55DE2C-AE1B-4E22-B802-AFBA7FFA2998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca94998f329eec96481c7c7c5525e7f1cca61732","datavalue":{"value":{"entity-type":"item","numeric-id":1316621,"id":"Q1316621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1329806$45A40A99-BD2F-4409-BDBD-6F10807FE260","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"9b06db24bb74bc636ef5ad374de2c6c3a0aa9573","datavalue":{"value":"Q127704448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$460EF788-FEB7-45BA-A528-6FFC036803B8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"828e2ac573d250b653b72cf18c9565f40ce50ca9","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)90096-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1329806$B3E9E55A-7110-4301-8418-CBDEB0B1FF64","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fa4ad423d3d57b467335dcdb8074179575248d08","datavalue":{"value":"W1991446038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1329806$D0C00216-D828-4957-9722-B4D0A6B1DB7E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1b3e775e1fe4213397aafdef949257bea74f191","datavalue":{"value":{"entity-type":"item","numeric-id":5006387,"id":"Q5006387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf907e1f6e62b6401f6ddcd4a961e20a4996c7b0","datavalue":{"value":{"amount":"+0.8024938702583313","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":"Q1329806$189614AD-4FA2-469C-867E-8FC6608C328C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8820ab984d9febdbb791cb7bb5571fc48350184a","datavalue":{"value":{"entity-type":"item","numeric-id":2706893,"id":"Q2706893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"061d6bc959b5d02533d787425a7ca1df3ecbc7e0","datavalue":{"value":{"amount":"+0.7849817276000977","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":"Q1329806$F64ABC1D-14E1-4319-A05A-738CA74FA95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c387e2c01bc9323ed1d68040082b31a13e3553b1","datavalue":{"value":{"entity-type":"item","numeric-id":1061751,"id":"Q1061751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78c9f07fc2b076c0ccf29b8b7699b47042a1dd1b","datavalue":{"value":{"amount":"+0.7691813707351685","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":"Q1329806$0CF5A8F6-DAEF-4266-AF50-6B40A7D9C3CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"288563260c3c3a19be8b84118e298212fd2efb30","datavalue":{"value":{"entity-type":"item","numeric-id":1898340,"id":"Q1898340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d75df759b4bec4509192e2ba36a4f4a7b4c2ead9","datavalue":{"value":{"amount":"+0.7560185194015503","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":"Q1329806$71803297-7554-4DA4-9C0E-4DD5E46EBB5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6643e7da48032682bc082a5e9d4edcf5c749c17","datavalue":{"value":{"entity-type":"item","numeric-id":1932457,"id":"Q1932457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00cfb0eda162125175631405fb5dce68e41486e7","datavalue":{"value":{"amount":"+0.7356551289558411","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":"Q1329806$8056C13F-0AA8-447A-ADDE-6B22E484A10B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Constructing colorings for diagrams","badges":[]}}}}}