{"entities":{"Q921012":{"pageid":922860,"ns":120,"title":"Item:Q921012","lastrevid":65397336,"modified":"2026-04-12T02:18:58Z","type":"item","id":"Q921012","labels":{"en":{"language":"en","value":"Graph coloring in linear time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4164897"}},"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":"Q921012$E6238AB5-A152-43C8-9A5B-2F9402F00D19","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5d8e29d5c09a7638e35c60db7e2ea4163d6714cc","datavalue":{"value":{"text":"Graph coloring in linear time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q921012$29E0ADD6-12DF-40C0-BA29-CA4F6AFBA609","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"dd55d791a06ebc15cb9365f0f8d34dad93ae7dba","datavalue":{"value":"0709.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$74EC92DA-601E-4AF9-AACC-2B01B7F2F4B0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dab6e6eed63c1edfb205614e413027b03f658429","datavalue":{"value":"10.1016/0095-8956(92)90042-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$44F45C52-1A20-42A4-928A-8A59DFCD4AA5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17fcd7139afa5567c823530fba22122acb06092a","datavalue":{"value":{"entity-type":"item","numeric-id":175498,"id":"Q175498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921012$15004F43-F382-430D-B2AD-57701162CDC9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q921012$4E97E3CB-EA06-489F-ADC4-9B4E41A21412","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ebf2f83ceb66feb8490ae2b363c9cada085a3535","datavalue":{"value":{"time":"+1992-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":"Q921012$5FDD2079-2D94-46FF-8EDE-D5C2B2729A24","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"80e562b5823307d0e779ec9e81d3285f6333a678","datavalue":{"value":"We provide fast algorithms for finding proper vertex colorings of a graph with a small number of colors, when a suitable orientation is given on the edges. Moreover, generalizing Minty's and Gallai and Roy's classic results on oriented paths and cycles vs. chromatic number, we prove new sufficient conditions insuring that a graph is k-colorable. The main idea in the proofs is to apply directed and weighted variants of depth-first- search.","type":"string"},"datatype":"string"},"type":"statement","id":"Q921012$42EF08D4-5B7A-4260-97F0-B54C0D62E71F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$3FEE5CAB-58BB-4AB8-B2A4-78EC2D9CCFE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$8E707A07-CC38-4EEE-B2D2-97A6E1F9E12E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$D4B27A41-5F9C-45B2-980F-2CA771823803","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0ac3619faca5a23d1d1f0fc67591629c835d9729","datavalue":{"value":"4164897","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q921012$DBBD11B5-DDF2-41FA-981A-06103F402DB9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q921012$E3809633-40A7-42B5-9BCD-F9CAEA2D08E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"318e95d2cea290f1765c519973e59af6e6b8d5b3","datavalue":{"value":"vertex colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q921012$BD300A11-D324-468C-B128-9E22F1A0709D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"458f12def83c1367a32fd7e7e1dd4b0d57985296","datavalue":{"value":"orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q921012$6D41FF43-5F2A-415B-9A1F-DBC784873BC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"952a8a56519402d383d63bdd5985e0123ef2349c","datavalue":{"value":"depth-first-search","type":"string"},"datatype":"string"},"type":"statement","id":"Q921012$994101B4-DCA9-41C8-8ABA-9F38A4E69CA8","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":"Q921012$F19BE1A3-0132-4463-AAAC-7C3618FE4362","rank":"normal"}],"P1643":[{"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":"54915cd4b6e35de98766ceefd093c10455db33b0","datavalue":{"value":{"amount":"+0.8200924396514893","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":"Q921012$54986BF8-52EC-4494-B07F-C7B0668A755C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0898846a5c344bac0d26f630c4f45b9dbaf215","datavalue":{"value":{"entity-type":"item","numeric-id":4019373,"id":"Q4019373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4de52697efcdd03d289fb2439194b31df80ec7f5","datavalue":{"value":{"amount":"+0.7978314161300659","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":"Q921012$93951EBA-3040-4412-8C4B-680C8971BAB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd536d34e5ba1e60e8271c84eec4a3a18b669cc4","datavalue":{"value":{"entity-type":"item","numeric-id":3815319,"id":"Q3815319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0fed3bbd41710e5853cd861cc35a416d624e2b4b","datavalue":{"value":{"amount":"+0.7908146381378174","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":"Q921012$8F1E9662-0AE7-45C5-B7B7-7F3D376845F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6791e35c160e3278e09e9f6ebb1bcdb315b9fc2a","datavalue":{"value":{"entity-type":"item","numeric-id":1264277,"id":"Q1264277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6d86d650c001a4d1a096472007a043a5c5e5d11","datavalue":{"value":{"amount":"+0.7907876372337341","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":"Q921012$406AF7FB-FE00-41DC-AEB6-A32C3F1A66DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"200e50955aa5d22c9fa2690b6a97a576c3b3a652","datavalue":{"value":{"entity-type":"item","numeric-id":1584255,"id":"Q1584255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b22cb7793d135aca7991b6895b251abbec5768f","datavalue":{"value":{"amount":"+0.7907302379608154","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":"Q921012$C2E0E549-8883-4ACA-AD5C-EA026BEF86FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph coloring in linear time","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_coloring_in_linear_time"}}}}}