{"entities":{"Q1322240":{"pageid":1332990,"ns":120,"title":"Item:Q1322240","lastrevid":70135845,"modified":"2026-04-13T12:41:25Z","type":"item","id":"Q1322240","labels":{"en":{"language":"en","value":"On the mean chromatic number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562642"}},"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":"Q1322240$8C514650-4604-458F-AC1B-67259EB39508","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef83ecafd7378c87793a60fb45af4ec56cb0b98e","datavalue":{"value":{"text":"On the mean chromatic number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322240$F14BC855-6A04-489A-BFB4-81EDBE46AEC9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07c99ddef3e72d96ebc9bac8a7d10f2edaddeb32","datavalue":{"value":"0796.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322240$BD94BEFC-05F3-4942-BE0B-15AEF63146F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb57238805f2573a59234ac5f7fb2d6f75d63bc7","datavalue":{"value":"10.1016/0012-365X(94)90139-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322240$E4EB6E2E-B436-43AC-8A97-32BDD41A550B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae0ca88e1940a7483721540124193708ea9c15bf","datavalue":{"value":{"entity-type":"item","numeric-id":260010,"id":"Q260010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$535B0A67-C18D-4016-B6BA-841F3F4E544D","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":"Q1322240$EC06BA0D-40E1-4F5E-94EC-0C1225D6A2DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d79d7cda91904207155cc49e8915318cb6203fb9","datavalue":{"value":{"time":"+1994-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322240$D1C7EC1D-BBE2-4A25-ADBA-E8C2179788F6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2d4d132a4255d3eb12e46ecaa46f64ef3170df40","datavalue":{"value":"From the article: ``Taking the colors to be the positive integers, the greedy vertex-coloring algorithm can be described as follows. The vertices of a graph \\(G\\) are ordered and the algorithm assigns colors to the vertices in that order, giving each vertex the first ... color which has not already been assigned to a vertex adjacent to it.''   The article cites results from the literature about the worst case performance of this algorithm and then discusses its average-case performance (over all vertex-orders) for two families of graphs: cocktail party graphs \\((K_{n,n}\\) with a 1-factor removed) and even cycles. A formula is given for the proportion of orders for which the greedy algorithm will use at least \\(i\\) colors too many, and asymptotic results are given which show that the number of colors used tends to 2 for the cocktail party graphs and to 3 for even cycles.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322240$533C4CB4-1A0C-48E2-ACFC-8C9569750F2A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322240$D9CCC76E-763A-4BEC-96BD-CFCEE4D90807","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5dc31cfc32e9e23a3dbe4fdda087995cea1c1580","datavalue":{"value":"562642","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322240$7D7F74B3-EFBA-41ED-9BA6-2150CC616609","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c490c61d3ebca1bb12e92ac3728ab71f1242daf","datavalue":{"value":"mean chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322240$35ED25A5-B11C-4B85-A1AA-3958982D2C56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42ac210e4abd13bc1486608ad927a0fbf3e7d249","datavalue":{"value":"greedy vertex-coloring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322240$0ADC9EF8-D97D-4459-979A-B5CEA4DEBFE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"332d26ee6734ad842f80cd7457ced8fae85596bc","datavalue":{"value":"cocktail party graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322240$6B3BB38D-53AE-4842-BD9D-45C8B212435A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7049b491993343a690a58a6055f9cf7bc3b64eb8","datavalue":{"value":"even cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322240$034FB839-8891-4D5F-AA02-7BFE821A2E8A","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":"Q1322240$E1DCE410-25C7-4790-A14C-E70BE215EF5F","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":"Q1322240$844B422A-382E-4D13-BCC0-4BED3535BBAC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc67ac131cd1c2f3e06cb715dcd3edec3019743f","datavalue":{"value":{"entity-type":"item","numeric-id":687131,"id":"Q687131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$4A293443-9E76-4D26-8690-EEBE95EE0B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d292ecc4b4eadbcc702a3801a336f637d4474971","datavalue":{"value":{"entity-type":"item","numeric-id":3035310,"id":"Q3035310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$10124728-0E48-44B1-8108-439871BA5BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b675c50d022de4ffb2551ea18bcd3c5f2e171dfb","datavalue":{"value":{"entity-type":"item","numeric-id":4711444,"id":"Q4711444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$97671984-162B-4214-A183-1F973A45C2D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b173dd40940f57ee7b8b2fb36e86b26a806a103e","datavalue":{"value":{"entity-type":"item","numeric-id":3983387,"id":"Q3983387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$E5256111-2BE3-4865-8F37-F31A0A60C62B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95f98b95de3fc63542346b5e5a52078a1b82904a","datavalue":{"value":{"entity-type":"item","numeric-id":3804717,"id":"Q3804717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$CB69B5D8-B1C7-441C-8FEF-8988F09E3FC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53adffcde85757731399caa2865fb984ffe87a55","datavalue":{"value":{"entity-type":"item","numeric-id":3815536,"id":"Q3815536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$F9A6D32C-F43D-4065-9F79-92C1087EB29F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f628172c25627c76e980e6b0bb5df4a8eddb2ea3","datavalue":{"value":{"entity-type":"item","numeric-id":2562785,"id":"Q2562785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$BB9289B6-FE36-4C1D-90A9-2A3B768FE418","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f7b8ca1457fe18226f427a3532d906202afa387","datavalue":{"value":{"entity-type":"item","numeric-id":3686952,"id":"Q3686952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322240$1325E783-E214-40DA-971E-66BC67B92BC8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"698d499fe2459196cb8eb91a07e1c3d2b19e602d","datavalue":{"value":{"entity-type":"item","numeric-id":3758854,"id":"Q3758854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b3a2d9e97952469fcc584362e9d512bc3a89f9d","datavalue":{"value":{"amount":"+0.92006934","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":"Q1322240$1C7AE09E-7C20-42AF-B647-446CC6412D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45362a60bd10ab06b3c4825c2463588696bbcbbe","datavalue":{"value":{"entity-type":"item","numeric-id":3501194,"id":"Q3501194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fe153c4e4835191e8a9023a45922231f8099b51","datavalue":{"value":{"amount":"+0.9160392","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":"Q1322240$A5648E38-9BEA-478D-BED4-8F7A100061EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19eda11abf9b15e3d307fa3acf371819fb6ec145","datavalue":{"value":{"entity-type":"item","numeric-id":5942344,"id":"Q5942344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"514532b982c90123d31cfd454a7c5005e4a77728","datavalue":{"value":{"amount":"+0.9156886","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":"Q1322240$F051D788-D9B9-40D4-8B79-11BB755D7F4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c466ebe712886494090688ed2b52ff33e27e4291","datavalue":{"value":{"entity-type":"item","numeric-id":687131,"id":"Q687131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db9dd1ae9abf8581db25e7bb5e60eafca7dc46c6","datavalue":{"value":{"amount":"+0.91184044","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":"Q1322240$E5122771-2D4B-4174-B21A-2C7CA223B1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00210f2d841a0b0db99c32ab7d72008249bacced","datavalue":{"value":{"entity-type":"item","numeric-id":3735722,"id":"Q3735722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bec99a31e6913afbf4bcee02eb2c08935ed228c1","datavalue":{"value":{"amount":"+0.9112962","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":"Q1322240$ABB1D742-3D58-4157-B056-880C06EAAD13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d480b6a657b9d34fc7640bac4612046df92f664","datavalue":{"value":{"entity-type":"item","numeric-id":4515856,"id":"Q4515856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce12508310ebba5a181ff080730eb7bc78d6cf75","datavalue":{"value":{"amount":"+0.909537","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":"Q1322240$CBF0F303-BDD9-474D-A193-C9523F6996D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e08f856defa1c5f670c437982036c8a60fb5c5","datavalue":{"value":{"entity-type":"item","numeric-id":626862,"id":"Q626862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35e3c8a4de984b099ca59d181fb8b37ffd536f4d","datavalue":{"value":{"amount":"+0.90546674","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":"Q1322240$07ED0DF8-B533-4785-B0C4-F957BB8A70E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1870f683af598fcb271b2899564dd9c4268842e9","datavalue":{"value":{"entity-type":"item","numeric-id":4053658,"id":"Q4053658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"040323b2e608fa7657c2e8e408e1a4efb27cb18a","datavalue":{"value":{"amount":"+0.9054438","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":"Q1322240$80494611-E608-4256-AB3A-A935E4DB2296","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f2d3930fe23f3d5a52a6e6ce5cb717998b55deb","datavalue":{"value":{"entity-type":"item","numeric-id":2716522,"id":"Q2716522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e69f97b310e28198e255834538ebef78e6f71f3","datavalue":{"value":{"amount":"+0.8977896","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":"Q1322240$4BA129BB-1D8D-44ED-9A27-CA786CA6B5A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the mean chromatic number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_mean_chromatic_number"}}}}}