{"entities":{"Q1180418":{"pageid":1191167,"ns":120,"title":"Item:Q1180418","lastrevid":66773088,"modified":"2026-04-12T12:46:06Z","type":"item","id":"Q1180418","labels":{"en":{"language":"en","value":"Effective on-line coloring of \\(P_ 5\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25769"}},"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":"Q1180418$0A6C9363-EAA3-4902-96F6-8B417664B107","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84a1c788e527a2af7a3b2978d71965fb52a3e9d0","datavalue":{"value":{"text":"Effective on-line coloring of \\(P_ 5\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180418$1F70A433-38CA-4214-8C17-E56CB264B82C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"36df856bb4ca60bfd0ddc09a691ca4e4be0d99ef","datavalue":{"value":"0751.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$3AFB8105-76E3-43CA-B80C-C4A7E931A77D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd1489cde5345965a10373418d77854b7b8ffaf6","datavalue":{"value":"10.1007/BF01206361","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$6AE91608-439A-48B4-A8C5-FEA4C2065562","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$9C274017-362C-466B-855A-9666DD5D4F76","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180418$9A793AA6-4BBB-477D-8CC6-BD669DEAA12B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"04d8b88cae4027be2d01b6ebd323afe2310d49f9","datavalue":{"value":"In the on-line graph coloring problem the adversary feeds the algorithm one vertex at a time which must be irrevocably assigned a color. The most common on-line coloring algorithm is the first fit (FF) algorithm that at each step assigns the smallest possible color to the current vertex of the graph. FF finds a chromatic coloring of any \\(P_ 4\\)-free graph and demonstrates a good performance ratio for \\(P_ 5\\)-free graphs. In the note the authors study another on-line algorithm that colors any \\(P_ 5\\)-free graph with \\(f(w)\\) colors, where \\(f\\) is a function of the clique number \\(w\\) of the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$B4DCE8EC-C45F-48BD-982F-D6D8E5A4BE5A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$09FBF6D4-82AD-4EC7-864A-D84A667F145B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$691089AC-26F6-413D-97BD-7E2CDB49FA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$80844A29-4EF2-4B0C-9E42-9AE31A04981A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dc5a02b4ec51a45af5c4510e7a49f10f939953f5","datavalue":{"value":"25769","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180418$99D12713-8DEF-43E7-9C2C-BB33518E48FD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$427BE830-9E83-4A18-9D72-BD1416E7DD12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb64e9a942dcfef0cece1bef1ae4d009bbcb3509","datavalue":{"value":"one-line algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$4ADAAC87-F727-448F-BCA6-7736C1E0FD98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07ba949ba77f5ef912b42b948b50744223cb3f6f","datavalue":{"value":"first fit algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$2BB6CDC3-8105-4EAE-85B0-CBAF400A03E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$FCAE3407-E0FA-44F6-AD9F-106DBD03130F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb2169375ebb26ec0067c3fe2ae2119dcb9b464e","datavalue":{"value":"clique number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180418$BA607B07-72DC-4276-8650-BCDD7CF9656F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3155ff163c931be8945149a68c11d68da0b397d6","datavalue":{"value":{"entity-type":"item","numeric-id":228779,"id":"Q228779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$4BFBC2F5-2189-4A2A-BDD3-4C2FA0BF22B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d40587e04768d5f70473e58fb8ddc324137351a9","datavalue":{"value":{"entity-type":"item","numeric-id":185069,"id":"Q185069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$292217A5-1814-49F5-BE4F-EDD5EBADC7FF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$09D68892-A774-4FD0-966C-533B86C98352","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":"Q1180418$286B1F76-A1DB-4B1D-AF7E-E9C305614BD6","rank":"normal"}],"P223":[{"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":"Q1180418$89A02C65-4CAD-4931-9D06-25FA9DC5DD10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac9c0a0496cac0485cd86316f1d46f4eb449c720","datavalue":{"value":{"entity-type":"item","numeric-id":1124602,"id":"Q1124602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$7090443C-8FCA-4F27-B5D8-10CA501BA54D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38a1643a3f55fd10ed31ef36d7cba0e5d3b84f16","datavalue":{"value":{"entity-type":"item","numeric-id":3932997,"id":"Q3932997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180418$2B985603-385A-4CAA-81C3-484AFEFA524C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"310a026cee8dcacfc106aff27693b6c32fb944b9","datavalue":{"value":{"entity-type":"item","numeric-id":4863971,"id":"Q4863971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60b483c01dd996fc31fedccca722c987b339141e","datavalue":{"value":{"amount":"+0.9319823384284972","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":"Q1180418$FE1371BA-09EE-4151-A475-12DE6BBD2C58","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":"138e0a9ab972b9b53e69f4e7e82a8b7d308187c2","datavalue":{"value":{"amount":"+0.8952024579048157","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":"Q1180418$4F65CD1C-0DFE-4853-9BAB-21B77D0873D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5992b879a8e4e10b92fa4187f2ef7b4b4ab7f9b","datavalue":{"value":{"entity-type":"item","numeric-id":2482722,"id":"Q2482722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c157a1b5faddddf3741cda36684e9fd5e9f6bf92","datavalue":{"value":{"amount":"+0.8693047761917114","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":"Q1180418$83A69016-BA37-4EA6-AB02-52F07DE1CDB3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Effective on-line coloring of \\(P 5\\)-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Effective_on-line_coloring_of_%5C(P_5%5C)-free_graphs"}}}}}