{"entities":{"Q5937920":{"pageid":8114722,"ns":120,"title":"Item:Q5937920","lastrevid":47642299,"modified":"2026-01-02T07:16:33Z","type":"item","id":"Q5937920","labels":{"en":{"language":"en","value":"A lower bound on the chromatic number of Mycielski graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1621229"}},"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":"Q5937920$83DDB9BF-D994-455C-B6E0-A40DA0BD9A58","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"546f2df5c43225605109eadffa6cc7f0a566bd7e","datavalue":{"value":{"text":"A lower bound on the chromatic number of Mycielski graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937920$06027C1D-ED27-4874-B5BC-902DB12D7E4B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dfc0b2381b194350cf9ac2e6a3d40e513a4b032e","datavalue":{"value":"0973.05033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$07AD8A0F-C7C2-46D4-9001-7AF1CFAFC47E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"43eeda065e17cbeb390978cc13ff1333f7463a8a","datavalue":{"value":"10.1016/S0012-365X(00)00261-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$49CB0364-2F8D-4CF0-8893-3F9543C25069","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2cdd1892625a16441d3991f7370b427d06f9bb5","datavalue":{"value":{"entity-type":"item","numeric-id":190512,"id":"Q190512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937920$8CBE4ECE-1D1D-4DE6-80F4-893BEA6D73F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"05f8aaa1fcaa350ea29e602aa878272ced422c6b","datavalue":{"value":{"entity-type":"item","numeric-id":190513,"id":"Q190513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937920$6DCFB153-3728-43FC-A48F-1BEF025409B5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937920$76D94FF2-3F8D-481E-873F-A03FBC842BDB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c5332c48de08b7b8da8f565721b384b6d4a11a4","datavalue":{"value":{"time":"+2001-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937920$A1D79092-4634-44F3-8C93-3FD013A393E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"790a40c0334a445885e2b26e367c2f29448b6769","datavalue":{"value":"The family of Mycielski graphs is widely used for testing graph algorithms. This paper presents a new lower bound on the chromatic numbers of Mycielski graphs. This bound is based on a correspondence between the coloring problem for Mycielski graphs and a multiprocessor task scheduling problem. The present bound is tight for the first eight Mycielski graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937920$A88EF81B-B2D6-4533-97BC-58127AFE5CB0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e77d710fff360ac5f5e834555bc2a388abb806e6","datavalue":{"value":{"entity-type":"item","numeric-id":409252,"id":"Q409252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937920$403ADD6D-83D5-40E8-8C84-707807F608C8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$7B97B3A7-F1FF-4068-8ACA-B1D314677739","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1908801a2431998085c7d582418a428f7e7f6658","datavalue":{"value":"68M20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$2F7FEDCF-63BF-4A21-8DB7-1BF66A40ABFC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83dd5ac57892d175d5e764af6a54ab959efe6e28","datavalue":{"value":"1621229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$CD3556C8-46F5-4EA1-95A5-0602E2118224","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"190020a062ea7976dd2c2c2049d08ea6e8778a2d","datavalue":{"value":"lower bound of chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937920$0A05E79D-E9EE-4CDD-A539-97CE55EE810E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f371dc0947f5d12eb6074ef5ec2c5635c30ee7b2","datavalue":{"value":"Mycielski graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937920$E4B0971C-E75C-469A-A6C8-D2C805D00B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d966a243a92d5d50d67cfb18cc6a40f8101cc49c","datavalue":{"value":"multiprocessor task scheduling problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937920$C66D8EF6-6993-4CA8-BA35-BF0050341611","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":"Q5937920$E1116D61-5B4E-480B-867E-6F3732D42D6A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ae7c0cae47ab61b5e56a96ba68cbc25ad97b856b","datavalue":{"value":"Q127109605","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$991CCC4C-AD60-466E-9F01-E1F7BE6A545D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67a2f21587f4a5470df61d1d16f55b79335008a8","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00261-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q5937920$22C5804E-4110-495C-8F95-5840BD2DAFA8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3662d7bb73e1a48ffcf20d8c50c2daed511a0c28","datavalue":{"value":"W1990260800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937920$E01E24A2-4A82-40FC-B7B8-415CD960B8BD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"862dcc2c4339587327be7bf63816efc03cb80699","datavalue":{"value":{"entity-type":"item","numeric-id":2823201,"id":"Q2823201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"869e9e6d5610c554972a910eae920494db71664e","datavalue":{"value":{"amount":"+0.7815976738929749","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":"Q5937920$3301F233-8776-4E64-9AB7-E5E42B692ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5b946a7a81a3fc918010e1f94dc4d9d310251c","datavalue":{"value":{"entity-type":"item","numeric-id":5920576,"id":"Q5920576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"459e6d3b5dacc51d526296b805127b52348c5aa1","datavalue":{"value":{"amount":"+0.7733023166656494","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":"Q5937920$489ECDB0-E6C4-47EC-8D1E-161327D42B74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e71b4aa7a6cac001f8f4f5b4895991ceeb8ec218","datavalue":{"value":{"entity-type":"item","numeric-id":5498278,"id":"Q5498278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a46a2a0cfd439aa63985676be77fae93d3cb96e","datavalue":{"value":{"amount":"+0.770599901676178","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":"Q5937920$02EBC936-5A6E-4315-9411-B5E06AA5C158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72495af89cb8e9d1523adab60a69520df35b3cda","datavalue":{"value":{"entity-type":"item","numeric-id":2865727,"id":"Q2865727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c92da7ac91d962582c1f183917dc152ce6aad280","datavalue":{"value":{"amount":"+0.7692985534667969","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":"Q5937920$5AF4AE2A-F3E0-4B4B-9221-368B074CC18B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a8179f7f68125ae96f23994d2943e24b241bf86","datavalue":{"value":{"entity-type":"item","numeric-id":4698090,"id":"Q4698090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11aa1edfb8d80d850ed042ff580884bd99ccd4b2","datavalue":{"value":{"amount":"+0.7602809071540833","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":"Q5937920$314770E2-B3BE-44DA-A41D-A3EC3D0F85E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5937920","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5937920"}}}}}