{"entities":{"Q5942344":{"pageid":8119146,"ns":120,"title":"Item:Q5942344","lastrevid":47661109,"modified":"2026-01-02T09:04:05Z","type":"item","id":"Q5942344","labels":{"en":{"language":"en","value":"On the chromatic number of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1638272"}},"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":"Q5942344$113295FD-1C99-4A55-9798-11E88882AA89","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dcb9bbb4975c7d13d4b01d00fa087630592a701f","datavalue":{"value":{"text":"On the chromatic number of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5942344$824F16C8-4323-416A-9726-CC2D0F0F6088","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c73c0aee0e5e194c1af084d15dab19449fd5e254","datavalue":{"value":"0977.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$68BD2C1B-8804-4513-B168-3EB76C47C133","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"94370cdcb8f112506c5be03ee66979a620df46e1","datavalue":{"value":"10.1023/A:1017557620292","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$DDAB9255-BAAD-488A-9753-3A723F2A2BA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f829d3f834a775a5035e081307d9496269e7aa3","datavalue":{"value":{"entity-type":"item","numeric-id":1870384,"id":"Q1870384"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$62610CE3-5900-4477-8493-B2C6D2AE0A1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8d740bdb1c395c49e0671f6584525a8aa0cf0dc","datavalue":{"value":{"entity-type":"item","numeric-id":691419,"id":"Q691419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$CA14BE1C-F484-4E28-B0E8-3965E7221A9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae97bc4877ac0397e1758940b0c6a6662202316b","datavalue":{"value":{"entity-type":"item","numeric-id":167615,"id":"Q167615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$E141CDBB-21A3-42BF-8343-5C2D58116B83","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a3c8bf4d8569c126380a9fc42f55609089e776fb","datavalue":{"value":{"entity-type":"item","numeric-id":82026,"id":"Q82026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$8BE56BAB-30CF-4641-8A99-0005482D0FFF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf47f0c2f8921918b490b998264be36172ab63f7","datavalue":{"value":{"time":"+2001-08-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":"Q5942344$0F7D0AAE-568A-4C8E-A6C0-28BBC3A00C01","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa5e9959ea2b7fb007ea15b90b06467bd0078c37","datavalue":{"value":"Computing the chromatic number of a graph is NP-hard---in fact, it is NP-hard to colour a graph with fewer than twice the minimum number of colours [\\textit{M. R. Garey} and \\textit{D. S. Johnson}, The complexity of near-optimal graph coloring, J. Assoc. Comput. Mach. 23, 43-49 (1976; Zbl 0322.05111)]. For large graphs, therefore, one must be content with an approximately minimal colouring. But to test an approximate colouring algorithm, one needs a wide variety of large graphs of known chromatic number. The first method of generating random graphs of known chromatic number appeared in [\\textit{F. T. Leighton}, A graph coloring algorithm for large scheduling problems, J. Res. Natl. Bur. Stand. 84, 489-506 (1979; Zbl 0437.68021)].   ``In this paper, a new 0-1 integer programming formulation for the graph coloring problem is presented. The proposed new formulation is used to develop a method that generates graphs of known chromatic number by using the KKT optimality conditions of a related continuous nonlinear program.''   Reviewer's remark: This reviewer would have liked to see a discussion of the advantages of the method presented in this paper over the one in [\\textit{F. T. Leighton}, loc. cit.] and either a definition of the term KKT or a reference to such a definition.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$2760681A-0599-4925-BC47-CC439668DDCF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$505B0070-B4D6-46BE-9698-3177899734FC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$D34730E4-A83C-4A89-AB95-C3995C491A1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$41C2EE31-D127-46F3-A824-81670AEC2C7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$215670C5-7132-440B-8E09-3DDC84A73582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$627064B5-A838-4359-A385-4EF603489C6C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cac94d12d924bc17bb9b09c5e87fe5172bfa81a0","datavalue":{"value":"1638272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$D279D3D9-2C80-4798-9849-05E3A23E2F95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c123c988a4455db85cc065f2e06e0a8051be65dd","datavalue":{"value":"combinatorial optimization","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$EE0A64D2-F144-4B38-9494-87D007C80621","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34e75612d514eb1a5f612f0afb0d2f17446ac17b","datavalue":{"value":"test problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$08DD4802-4E35-4986-B2FD-14EB02672B56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$19CE2EFF-6B5B-4BDC-AA68-8016125FFE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8df57be8c106df4fbe375ad2ff9851f149c079","datavalue":{"value":"colouring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$D3EF56D7-947B-472E-9941-8FFA474BEE8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0a438e9092bcf192a5c493b52b0717e88c2591","datavalue":{"value":"integer programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q5942344$61FB8E42-A4F5-4A51-BE4B-BD36F104CE0D","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":"Q5942344$37021964-B38D-491C-AC33-534B6EE38213","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"31b0e6148c6711b4917a5d908c6a1cefaaa1c6b4","datavalue":{"value":{"entity-type":"item","numeric-id":759645,"id":"Q759645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$A43DB635-E331-4F25-87B2-AA66C6E5B796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32669c9303b6fcfce30a867e0ec9585dd818044e","datavalue":{"value":{"entity-type":"item","numeric-id":3878752,"id":"Q3878752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$65DDB42E-281F-4C34-8EAD-C07D042C23BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1d22e95cfb08114972c1514e26bef4d87d04d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5524918,"id":"Q5524918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$174CF548-0C1F-47FF-9F2B-EFC036639D4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2d4603f2a57548ee0289a818b11f0d65def71c8","datavalue":{"value":{"entity-type":"item","numeric-id":5589132,"id":"Q5589132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$2303B44F-71DC-4A4A-BC16-FD9BEFFE2509","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e05d8b0e7bd4732033e5b7dfb70c9ece2bb97cd","datavalue":{"value":{"entity-type":"item","numeric-id":4770742,"id":"Q4770742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$D47BA923-B7DB-43CA-8F1F-2A054B8D495C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"272feb29f84531908baaef13f0baaf1fc4d2094a","datavalue":{"value":{"entity-type":"item","numeric-id":5668500,"id":"Q5668500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$D78AFCAD-FE69-452B-94FE-FB2B1B5BC1C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf299df746ac7cc81b503f55f44e7da24ec4f0e7","datavalue":{"value":{"entity-type":"item","numeric-id":3924236,"id":"Q3924236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$90E8ADDD-4D51-43B0-89B1-C5330FB746E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"992fe2453dc869da6f244afa2052bf59de941320","datavalue":{"value":{"entity-type":"item","numeric-id":3042292,"id":"Q3042292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$E002843C-F325-4D0E-BAFF-E41685B45BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$1F0C1705-C7AC-44B6-9B05-8775056F2356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc4f0630ec86e5a0d3e96a9ce7ec4c2915d07620","datavalue":{"value":{"entity-type":"item","numeric-id":4083458,"id":"Q4083458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$45B04F1D-6013-4590-851A-B32FB025F50A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4e7b26f6765114b169da5a79770389fa5bd84e12","datavalue":{"value":{"entity-type":"item","numeric-id":4175306,"id":"Q4175306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$53CC620D-0B67-4FE2-BF81-BC56DEFFE933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67478757af9fe779b10ecfc5781e9a866684fd86","datavalue":{"value":{"entity-type":"item","numeric-id":5670645,"id":"Q5670645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$87DD8BBB-30D8-4C9D-B078-9A9BBFFF4C2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8205d99991e663bd0841aadc5bee21beef2c309a","datavalue":{"value":{"entity-type":"item","numeric-id":581241,"id":"Q581241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$60DBEEEE-A9C4-44FD-B5E6-DB6601F9CE76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e9c86360d4b592a623a32491be38570987dd4b6","datavalue":{"value":{"entity-type":"item","numeric-id":3978838,"id":"Q3978838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$FCBED631-E5D3-4DF4-85CD-648CB265AC85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"998fa1ebf7e2adcc8d4bd8755866fb77de95480a","datavalue":{"value":{"entity-type":"item","numeric-id":1188890,"id":"Q1188890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$29566216-DF32-4382-B877-E84D7D1395C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"540585b8ab5220220a5d04fafeb3f93c8aaadc05","datavalue":{"value":{"entity-type":"item","numeric-id":3028740,"id":"Q3028740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$A774FEC2-3A40-4079-80CE-ADE963DAAE32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52e5fe3c734425bb98ff24f9b64507dde573f0e3","datavalue":{"value":{"entity-type":"item","numeric-id":1203071,"id":"Q1203071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$59AAD59F-33A7-4C96-8E70-EEDCFB12B918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6243260520151bb8bfe470d151c18f2e54f20820","datavalue":{"value":{"entity-type":"item","numeric-id":4371555,"id":"Q4371555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$1AC1A2CB-3B95-40E4-9ADF-83F5A007F5B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d792d7a814e621b32660e5bc12bcdf6e7b4af22","datavalue":{"value":{"entity-type":"item","numeric-id":1310979,"id":"Q1310979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$11EA5D4E-D919-4990-8B8C-35154299418B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fd2865c347636a0d54c9d361e775f17ea6bdafc","datavalue":{"value":{"entity-type":"item","numeric-id":3932576,"id":"Q3932576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5942344$3D6903DF-7A37-4780-829B-089FFF340B23","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8efa528c5d1c7fdb086105ea3b7581760c6b1dd1","datavalue":{"value":"https://doi.org/10.1023/a:1017557620292","type":"string"},"datatype":"url"},"type":"statement","id":"Q5942344$96003E7C-53FF-466B-9D27-C82A39ACF73E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f057938ef77aad4151388210ca93b7b957c19ae7","datavalue":{"value":"W2111989082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5942344$203A8763-D3CF-4E0A-8067-1CE7BCA3AC1B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a0380154964293e12482505fd34e4e9d84e8685","datavalue":{"value":{"entity-type":"item","numeric-id":5932643,"id":"Q5932643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0097dae5854d27375f9daf11a5815061edf38232","datavalue":{"value":{"amount":"+0.7809715270996094","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":"Q5942344$527B11DB-24EA-48AD-B3AB-E9292A3139B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"62de1ea534604ed2684d45258e99e651c423405e","datavalue":{"value":{"entity-type":"item","numeric-id":3119055,"id":"Q3119055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09780f0493b2f1ec8e667c2d3b10bcbe7b7f385f","datavalue":{"value":{"amount":"+0.7721218466758728","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":"Q5942344$C8BE88F0-7B74-43AE-AA73-A9EBFD569E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5863cbd970b66254fa5dbd296e736a1519cd0f60","datavalue":{"value":{"entity-type":"item","numeric-id":1116349,"id":"Q1116349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7ad90341dce822a294af2109fa50dac718ceb19","datavalue":{"value":{"amount":"+0.770841658115387","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":"Q5942344$89C4564C-5591-4B18-8B71-5D783C1624A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b344a923609afaef5b7f1c7d506a3b06d159759","datavalue":{"value":{"entity-type":"item","numeric-id":3078472,"id":"Q3078472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4027a855eac67c252f53aa16db3904134be64fe3","datavalue":{"value":{"amount":"+0.7695255279541016","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":"Q5942344$2B26AF84-F6FE-4708-8A51-AF34BA9EB7BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a1b22bc61fef8e3c6451ceda2631e6d87cb2064","datavalue":{"value":{"entity-type":"item","numeric-id":5463425,"id":"Q5463425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e3bdedfb71c6852985c16e0a598552fa63cd97b","datavalue":{"value":{"amount":"+0.7691831588745117","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":"Q5942344$324AFC16-0C8A-4D84-8AE8-D1427C970DDD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5942344","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5942344"}}}}}