{"entities":{"Q1124602":{"pageid":1135351,"ns":120,"title":"Item:Q1124602","lastrevid":66184107,"modified":"2026-04-12T08:06:41Z","type":"item","id":"Q1124602","labels":{"en":{"language":"en","value":"An on-line graph coloring algorithm with sublinear performance ratio"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4112619"}},"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":"Q1124602$7DE5467E-A5CB-4015-B783-8F15F8A3784F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc2bb730fcfec034500f6fb6d4902603197969c4","datavalue":{"value":{"text":"An on-line graph coloring algorithm with sublinear performance ratio","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1124602$5924B197-60C9-43F0-ACB5-5961D2402557","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83a3d785edbcc87e82c8e98b8474256b576fa160","datavalue":{"value":"0679.05031","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124602$EAA69C50-2697-443F-9434-1F27F48B60E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8930f20baf6a4526ae3c914a53e8550a79601f13","datavalue":{"value":"10.1016/0012-365X(89)90096-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124602$ABD4D929-4FC4-47DD-8220-C434C236CA67","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"93f09421b6aff8e8d7720ab7e9d35f10a9deb5a2","datavalue":{"value":{"entity-type":"item","numeric-id":1112076,"id":"Q1112076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$EB02442C-2142-449D-9BB9-F579E73AE5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a539e6b59a5781e06906f6b0f6a357a21edb017","datavalue":{"value":{"entity-type":"item","numeric-id":792346,"id":"Q792346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$EBFD4A81-74ED-434F-B4E0-53020F04A697","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"201364cbbc61e0d0a85431778d2e1c2e76306b69","datavalue":{"value":{"entity-type":"item","numeric-id":6480584,"id":"Q6480584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$DA43D3F3-98BD-4391-BEA7-BA19F0E084DA","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":"Q1124602$E3208DC7-82C2-47B0-929D-A1E3FA69FB3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1124602$74575A98-808E-4159-A4E7-4F1AFEAFE561","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5fb402bfe584f0905c57f99d6928803e975b0b9c","datavalue":{"value":"In an on-line graph algorithm the graph is presented one vertex at a time. Each new vertex is given together with all edges joining it to previous vertices. An on-line coloring algorithm assigns a color (positive integer) to each vertex as it is received and, once assigned, the color cannot be changed. If the integer assigned is always the least possible, the algorithm is the first-fit algorithm. If A is any graph coloring algorithm then, for a graph G, \\(\\chi_ A(G)\\) denotes the number of colors that A uses to color G. The performance ratio of A on G, denoted by \\(\\rho_{A(G)}\\), is \\(\\chi_{A(G)}/\\chi (G).\\) The performance function of A is defined to be the maximum of \\(\\rho_{A(n)}\\) over all graphs of order n. The authors report that Szegedy (unpublished) has recently shown that for any on-line algorithm A and integer \\(\\kappa\\), there is a graph on at most \\(\\kappa (2^{\\kappa}-1)\\) vertices having chromatic number \\(\\kappa\\), but for which the algorithm A requires \\(2^{\\kappa}-1\\) colors. Thus the performance function for any on-line algorithm A grows at least as fast as n/(log n)\\({}^ 2\\). The authors demonstrate the existence of an on-line coloring algorithm with performance function \\((2n/\\log^*n)(1+o(1))\\) where \\(\\log^*n\\) is the smallest \\(\\kappa\\) for which the \\(\\kappa\\) times iterated logarithm, base 2, is at most 1.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124602$6EE5744E-DCA4-46B8-98DB-B2A5D123183C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124602$232685DA-B46E-4336-B88F-D6B75BDD212E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124602$68D49F45-2822-4074-B324-3C616105344B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"67bc95e9d3cb5bfc655af90e0a32420e95dd057a","datavalue":{"value":"4112619","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1124602$67925F75-1459-4189-BD9E-4D0B133A8327","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf75731eb23a19d44c86e48f5149e990f3838964","datavalue":{"value":"on-line graph algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124602$6181EFC3-1A82-4FF7-8011-3FBA870866D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"adefb1e87cd04cb53e8c70511206c1ec9ee6ed74","datavalue":{"value":"on-line coloring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124602$6EAC8B8B-9A1B-4D38-A3FF-AEB361F9FEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0680f2ed27102d2430ef4f36846a764d756f0a60","datavalue":{"value":"first-fit algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124602$2964BC6E-6E47-48EA-8B75-89DD63468968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1124602$F1C58A09-091D-4222-940D-3F47A2F6A81D","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":"Q1124602$A38513CB-8382-410D-B7A1-9F5448F812A3","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":"Q1124602$A40BA928-A700-41D0-A68E-9E8A52640283","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"55b9ff904e1c98a6431855b40a7e673c55670f79","datavalue":{"value":{"entity-type":"item","numeric-id":4097267,"id":"Q4097267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$A68FE616-788C-4400-BF82-4C49EE59891A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4934bb2301da1a902e1805090c5568d9d86ab7b","datavalue":{"value":{"entity-type":"item","numeric-id":4178468,"id":"Q4178468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$F46C7B77-CFF1-4E02-9DE9-58FE2AD83F02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2fcdeee3f2144f996b53360c8c07ab4f5fbb9f7","datavalue":{"value":{"entity-type":"item","numeric-id":3785965,"id":"Q3785965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$D82AF115-EFD6-4EED-B181-75C96B1C74DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe89cc879c98c5f68fc2110c10e3f7a543a2c9ae","datavalue":{"value":{"entity-type":"item","numeric-id":583245,"id":"Q583245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$FA23ED57-DCE1-4F98-BDA1-5AC54598988C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a84ca05055b81b1d4477c12adf902e5f849b5539","datavalue":{"value":{"entity-type":"item","numeric-id":4051589,"id":"Q4051589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$F0B2838D-DA66-4D3D-A05D-3574911FF233","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de43f3e978a9ce24db65e773f8fff3d02c7dc139","datavalue":{"value":{"entity-type":"item","numeric-id":3944587,"id":"Q3944587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$F98AE7C6-505E-4547-BA5B-B673B635074C","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":"Q1124602$139E2274-28E8-43A7-BF27-849B0C645CBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"053ffe8d65e0994d475a368e3c3296b25479e09b","datavalue":{"value":{"entity-type":"item","numeric-id":2266723,"id":"Q2266723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$A7B5EBAE-CABA-46F8-B9BC-20AF213B56B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b686b6561b404abd99050b38d4f468b71b973a86","datavalue":{"value":{"entity-type":"item","numeric-id":3950561,"id":"Q3950561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$187E9CBA-EBF2-47E8-B1AF-10653AC6C199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2708e882937281b237ad6578d98e4eb2b386f2","datavalue":{"value":{"entity-type":"item","numeric-id":4079040,"id":"Q4079040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$FAC9E4DA-6BAF-47AF-A2A1-5D6838DE0640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"950ae927e9d33fb9daf6bd71fd5d7a51726a8270","datavalue":{"value":{"entity-type":"item","numeric-id":3679213,"id":"Q3679213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$6E6E0856-FADC-41C9-B6AE-D646D5AAC026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00910816ba034b6655b7a47d13d1206cc1d40ae2","datavalue":{"value":{"entity-type":"item","numeric-id":3735083,"id":"Q3735083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$6932876E-95E2-49A4-81F3-4418F7C3DD98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8aaede631bfdc54d481cb5dea09d28a4412b7","datavalue":{"value":{"entity-type":"item","numeric-id":3763600,"id":"Q3763600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1124602$9492B5DD-511F-4850-B4E3-8C964DF0E0A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ad34831a710ad4e170fdf8edd7b65633995398e","datavalue":{"value":{"entity-type":"item","numeric-id":4763409,"id":"Q4763409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b1ba54ffc3f885a9445a580577e1c34b0b8494b","datavalue":{"value":{"amount":"+0.8843991756439209","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":"Q1124602$E1EE4159-44A3-495F-AE0D-9A94D5C044CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd4da08196384e5fe6bde6f548d9f7ffb80b97ed","datavalue":{"value":{"entity-type":"item","numeric-id":4015271,"id":"Q4015271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f8d79e0c40716a1c2e582ed76213c88e82a5511","datavalue":{"value":{"amount":"+0.8828551173210144","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":"Q1124602$6F568621-E8A6-4D8C-8F90-32FC4AB97CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9d3406c5d1c9db92dd2aae8d00ec54f28079e1c","datavalue":{"value":{"entity-type":"item","numeric-id":3804717,"id":"Q3804717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"faad81657fefcb58b72922c23c5acfef14c197a9","datavalue":{"value":{"amount":"+0.882697582244873","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":"Q1124602$7F5FCC7C-3109-4122-A7DB-09807E7B2921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0bd9200ec83a517e6c709443ac8bb176766574d","datavalue":{"value":{"entity-type":"item","numeric-id":1312187,"id":"Q1312187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"788027facfc8cd7cd5cffa6381254476edd8b816","datavalue":{"value":{"amount":"+0.8807567954063416","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":"Q1124602$E35BAAE0-3722-4F4A-B9F9-DACA9168E046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0972b0daacd9cf6d8eb42f8c2cb39a432b1079c1","datavalue":{"value":{"entity-type":"item","numeric-id":4010310,"id":"Q4010310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fc06d3771f5144ffea9acc96377fdca51683339","datavalue":{"value":{"amount":"+0.8767988085746765","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":"Q1124602$9A437E7A-3BE2-406A-AF3B-5C1EBC7EC8B2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An on-line graph coloring algorithm with sublinear performance ratio","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_on-line_graph_coloring_algorithm_with_sublinear_performance_ratio"}}}}}