{"entities":{"Q1967115":{"pageid":1977857,"ns":120,"title":"Item:Q1967115","lastrevid":72071808,"modified":"2026-04-14T02:28:15Z","type":"item","id":"Q1967115","labels":{"en":{"language":"en","value":"Online coloring known graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1413183"}},"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":"Q1967115$EA7DC96D-AEBB-4F3B-B374-3FF35C9EA981","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"062a8ed45ca7879af2d4a931780900cda6459759","datavalue":{"value":{"text":"Online coloring known graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1967115$2C7B2ACF-EFE2-4710-844F-5BF33B6A31CD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8cf07e8edd2ffc5c4116319663571a0caf3f7f9","datavalue":{"value":"0940.05030","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1967115$16C248BE-FC36-4400-831F-A7616782D036","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"411282777dd6b69232cfefb6c570cb3fe6b91ce0","datavalue":{"value":{"entity-type":"item","numeric-id":235185,"id":"Q235185"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1967115$4B3D5888-B69F-4365-A4E9-717CB370C7C7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1967115$8A762B79-21EE-4F52-93A3-2732E6EC16C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"176d573220319023c9183a0db13102ca32315746","datavalue":{"value":{"time":"+2000-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1967115$28DB18D6-6484-46CB-BA42-686FBDF89711","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d9c8e3ea2ddcb2ef5753ada2b18a450c3e534a4","datavalue":{"value":"https://eudml.org/doc/120387","type":"string"},"datatype":"url"},"type":"statement","id":"Q1967115$2C47BCF7-35BA-4C49-9ABF-1968816A02A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"609684d73d99099ae4518125d0d0d9d4d166c2e8","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r7.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1967115$CB31715C-0ABE-4C49-8B88-6440A4991B1D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"51600d4360c534753d3e967941cd48cea16b41ed","datavalue":{"value":"Summary: The problem of online coloring an unknown graph is known to be hard. Here we consider the problem of online coloring in the relaxed situation where the input must be isomorphic to a given known graph. All that foils a computationally powerful player is that it is not known to which sections of the graph the vertices to be colored belong. We show that the performance ratio of any online coloring algorithm with advance knowledge of the input graph is at least \\(\\Omega(N/\\log^2N)\\), where \\(N\\) is the number of vertices. This matches and generalizes the bound for the case of an unknown input graph. We also show that any online independent set algorithm has a performance ratio at least \\(N/8\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$2538F256-B93C-4E52-B409-1A1DDC19461C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1967115$60D46BAC-40E4-40A5-8F8C-29BDEBE8F9CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1967115$5E6B6F28-7FCA-4121-B35F-CB64C8D12E05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eb52cff132d024e8df3b602f4f014f356d4be80c","datavalue":{"value":"1413183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1967115$70EC7E95-65C0-40E3-929E-DFBFA2ECF852","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$3AEC0582-78A5-495D-9B7A-1D8292F00CF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0fca5ac8cddc8f74e7908fc7842929c55342241","datavalue":{"value":"online algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$7AB2C24D-E5EA-4E21-AA52-A3389BD1F7F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac888510ead4bb80cde4924072b8be814e4b065","datavalue":{"value":"online coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$4C935021-6DD6-4B63-A0AC-702F3CAF7277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16450eba9d9bd1b4b2cf662c9befb88d27ffbbc4","datavalue":{"value":"performance ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$88F06C2D-57EA-40EB-9950-59D9B2E60590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c3c1f7def14b7fac0619903a2b6f0bcf745fc5ae","datavalue":{"value":"online independent set algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1967115$A993121D-3BA0-4DE6-9F2A-44B242301503","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":"Q1967115$5913F326-3ABE-4A59-95E5-72617C43777B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"fa25b57e752ec2fd3d0d9c5b2c6773f43a1b09e8","datavalue":{"value":"bafkreievj3se3v54bxhe5fjcjjnfcacp3nu7hadnlcsanlquze2tbxdv34","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1967115$4B36114B-9826-4CA3-AFC5-6D9A4FD44D0C","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":"713bdf5ba46feb9c50ad4fe649453e4e38a43619","datavalue":{"value":{"amount":"+0.860257089138031","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":"Q1967115$1CE30B6F-51E5-49A7-BEFA-EBEC50728B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ee13c99bbb0ba5047ae010aed223ca4989f8f12","datavalue":{"value":{"entity-type":"item","numeric-id":2223701,"id":"Q2223701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ba735ffa5a9f8b268e958be26d9be1899ddc74c","datavalue":{"value":{"amount":"+0.8588452935218811","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":"Q1967115$6FF31895-E15A-42C2-824D-1DE718B7B655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9299893d837020e11468fd61a82288380538d549","datavalue":{"value":{"entity-type":"item","numeric-id":1331951,"id":"Q1331951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252c8e8ab5143f0dc46cdf9de69c6134c362e094","datavalue":{"value":{"amount":"+0.8454750776290894","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":"Q1967115$9BCA6204-57D8-4ADA-8E21-1F44070B2701","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":"29c0d0f1b77106cc009d54f830b474713d424cd0","datavalue":{"value":{"amount":"+0.8446332812309265","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":"Q1967115$1884943F-4C17-47DA-9F55-2A293171D5B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6f6477c4e60b902cc82b071b6df1d8fb53b2fd5","datavalue":{"value":{"entity-type":"item","numeric-id":4010319,"id":"Q4010319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7794b80dde5a6ddb649f1012a90b79e3cb01619","datavalue":{"value":{"amount":"+0.8440777063369751","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":"Q1967115$61C137AC-F98E-4B1E-B16B-91E7CAEDD590","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Online coloring known graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Online_coloring_known_graphs"}}}}}