{"entities":{"Q1811065":{"pageid":1821807,"ns":120,"title":"Item:Q1811065","lastrevid":69020760,"modified":"2026-04-13T03:46:58Z","type":"item","id":"Q1811065","labels":{"en":{"language":"en","value":"Parameterized complexity of vertex colouring"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1925248"}},"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":"Q1811065$0D19B5CC-B7C6-4398-9E59-D6392EDCD9D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"99ca04d4e1c70f4b36e910c4672ca0f0c4f93de4","datavalue":{"value":{"text":"Parameterized complexity of vertex colouring","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1811065$1B27D0ED-76C7-4035-B3F4-16002F0A29C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"78711a33a3d02d213448a93ad5e3f91071887b3c","datavalue":{"value":"1015.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$BFCE9729-216D-43E4-83A1-4284E29C9734","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"57324c7908619d7b8daeddf0e3ec0122aa8fea4f","datavalue":{"value":"10.1016/S0166-218X(02)00242-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$93D12745-0495-42DB-971D-E604DB732D5B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f00237d5739b07662cb51e9e957100249e47b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":175508,"id":"Q175508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$E3613674-73CE-45D8-8638-BFD07AFB0AB7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$450238B3-0172-496F-BDA0-8F1B7567FE4C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ae38298a411e50615364cd6c80d7e0f949b3a896","datavalue":{"value":{"time":"+2003-06-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1811065$0CC1E929-E542-4960-ABD0-4053C174F50B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1cf2419898c7625f3e0fe8bc99f03194e8ae015f","datavalue":{"value":"This paper studies the complexity of the vertex coloring problem (assign as few as possible colors to the vertices of a given graph such that adjacent vertices have different colors), for families of graphs, obtained by adding or removing some fixed number \\(k\\) of vertices or edges to a known family of graphs. Several results are shown. In particular, it is shown that vertex coloring can be solved in linear time, when a fixed number \\(k\\) of edges is added or removed from a split graph, and that it can be solved in polynomial time, but it is hard for the complexity class \\(W[1]\\) (from Downey-Fellows parameterized complexity theory) for split graphs with \\(k\\) vertices added. It is linear time solvable when one vertex or two edges are added to a bipartite graph, but becomes NP-complete when two vertices or three edges are added to a bipartite graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$6415D85B-63FE-4D41-AC44-E8FEA5DCAF9B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$0E6CEF94-6ABD-4FFF-A914-8691B07492A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$265FC06F-1FCB-4800-B32A-A45167012D53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$49F9FDF2-15BC-41CA-8B9C-A4521DE10BDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$34BF8285-2C5E-4D63-B401-54B99E840A12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$40765125-43A9-43DB-A650-D3B4743D0C79","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"721310ed743775db9d8762847c67a62132184272","datavalue":{"value":"1925248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$AA3289A9-79A1-4C41-A842-1AA0D0FF4F2D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"85dfdbd7a975d6137b355769addaba184ea21dc4","datavalue":{"value":"vertex coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$FD0D06E0-45C9-4400-8FFC-C6ECE6690B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c710347a51d35c0d33880f2536dceb5042923eb","datavalue":{"value":"fixed-parameter problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$F48E43B6-F2E5-4B1B-AEF5-2F95D52F2670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee63604621b6fd9d90b10f19ccdd9c167a66b1b6","datavalue":{"value":"parameterized complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$31A1B74D-D1CF-4243-9458-89AB8BB7B1A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8364c4db3fffd0a014142e381813cb4f26f28ac","datavalue":{"value":"split graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$C2CB8EC0-58B0-497C-A84F-C10389029C85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1811065$64F3C9B8-A1BC-4F6E-8412-06997EC14BC3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$1AE1C2D6-CD9D-41DD-9BF9-54508ABCC7BA","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":"Q1811065$838F01FD-9E98-4656-BC7B-AF1AA2EE2E07","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"770bb68de47752f527df3eb5fd0239815f0bd638","datavalue":{"value":{"entity-type":"item","numeric-id":3751595,"id":"Q3751595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$35983AC4-BF61-4FAC-B038-1963F595D8D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be17e3e16f8de4b41a5e87255873ed44ec5fd55e","datavalue":{"value":{"entity-type":"item","numeric-id":3361904,"id":"Q3361904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$303C1A1A-B31F-49EE-9901-9DD641876E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f96a660eaa4e8b33419c867ffedb789edb466ebc","datavalue":{"value":{"entity-type":"item","numeric-id":1116705,"id":"Q1116705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$6B90B4E9-41E8-4FD5-A3EB-7C6230791EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747a911f10480a7188a201d8808620458b2a3690","datavalue":{"value":{"entity-type":"item","numeric-id":5691297,"id":"Q5691297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$B43E437E-BDF2-4CD1-AC8C-BC855627C821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b96967c62a7a6d504927602aabf782afe843da41","datavalue":{"value":{"entity-type":"item","numeric-id":1343141,"id":"Q1343141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$BF7B7156-0B47-4589-87A2-71071C6CFF79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c694e31997a7a457bac1c2971d60584b887f7d1","datavalue":{"value":{"entity-type":"item","numeric-id":1352005,"id":"Q1352005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$C1D3EA33-3C46-47DA-9540-EBB9A7F36887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1134f2341d7e5000fd707505605e06ca29388803","datavalue":{"value":{"entity-type":"item","numeric-id":2641288,"id":"Q2641288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$D7BE56C3-5166-420C-AAA2-1310A0B24981","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"500bfeba9231a071c9bfde5b167ca0a56cfc8d2f","datavalue":{"value":{"entity-type":"item","numeric-id":673779,"id":"Q673779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$D01C06AA-1A96-4270-92C9-8C2C1C67082B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"befbfe541247817710e22716675e0c030f7b1dfc","datavalue":{"value":{"entity-type":"item","numeric-id":4503944,"id":"Q4503944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$7313419B-7173-4331-A7E3-8C10246C5404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$D3C1C0E2-EAE6-45D7-BAD1-75208288F6DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$29A97C43-6F77-4DF9-98E0-A86E880888BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$BB5F0390-7A0C-4311-A589-4F47DA847A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$EAA1BCB8-E56B-41DD-A968-FB3074A1D1F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$D2BB825B-E5D5-491C-B057-79513A284925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41cc6a286064615a5226bdd0939f0f85a946c13e","datavalue":{"value":{"entity-type":"item","numeric-id":1167741,"id":"Q1167741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$E043D2A3-469F-48E9-9406-DEAE36361218","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$815122B0-9315-459A-A314-71F56ED84469","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"785e7851fac401f47fc66697d0bfc439f0b289a0","datavalue":{"value":{"entity-type":"item","numeric-id":4368729,"id":"Q4368729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$15609A20-DB97-4BF5-B92A-260E33FDD886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f636f51cbaa04d93568a9d500475b5e9a7e29330","datavalue":{"value":{"entity-type":"item","numeric-id":1363645,"id":"Q1363645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$9E848BAB-F0AC-4A98-B973-9AA36CE0FE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$C3EB7568-1871-4B7A-AF2F-47E0858F3886","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d451bf1b8f711ef7f538cfdc1a090f03a5a95227","datavalue":{"value":{"entity-type":"item","numeric-id":4268849,"id":"Q4268849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$50AB9CFA-9F51-4235-85B9-7DDBF631A0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"653c259614e077cb879d928145409bb1fe1f9dd1","datavalue":{"value":{"entity-type":"item","numeric-id":4940046,"id":"Q4940046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$2B7AD65B-AC1C-4859-A8D2-FCE84D11ECB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5325820f1da9bdbe993d9d54d34a90dc88d69e8e","datavalue":{"value":{"entity-type":"item","numeric-id":4869540,"id":"Q4869540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1811065$4DDB8C69-5B81-4771-B389-54296CF71432","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4b4ed584017b2bccbd8cee6413914b5efaa3fa7","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(02)00242-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1811065$20A7A58C-C47A-44D2-AC45-9C98569622D9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"414c627d447064efcd36c2e43b8b3d49b28169aa","datavalue":{"value":"W2130673833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1811065$BDEDA10E-4C69-41AB-BA3A-B5C99733A93B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"302813c8d4ccb19e080a49ce84fb1faf31c2af00","datavalue":{"value":{"entity-type":"item","numeric-id":3630207,"id":"Q3630207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39d5f7e2bb995ed78f4625c86188e0d5de5510e5","datavalue":{"value":{"amount":"+0.8184982538223267","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":"Q1811065$56F830E3-5728-4765-91B8-2A4BF556622B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f86653d734c1c31192879da8cc249a58717cb6a","datavalue":{"value":{"entity-type":"item","numeric-id":534566,"id":"Q534566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"708268141ce6bdd71738750c8bc8ce6ddda9bf37","datavalue":{"value":{"amount":"+0.8164725303649902","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":"Q1811065$6B80A20F-35C8-4A98-87A8-5C116C89DD49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"770e5b112d5066ebe882eba7399fdc5905ded8a3","datavalue":{"value":{"entity-type":"item","numeric-id":3522947,"id":"Q3522947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6f5c8b8b6afaaa0cfc4d25cd29d8b5edd5df4c2","datavalue":{"value":{"amount":"+0.8075091242790222","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":"Q1811065$33F85E6F-CCA8-46DC-BABC-4585DD1D6952","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a14407743d48d3795364302c5cb9be7ff68db56","datavalue":{"value":{"entity-type":"item","numeric-id":3088272,"id":"Q3088272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4738df3d0a0a50fccdce48115cd017eafac5d3f1","datavalue":{"value":{"amount":"+0.7966415286064148","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":"Q1811065$2325816D-D134-4C87-B5A0-147A68AA83F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2380bd15ee6a039b8b33f282c85bdd39c9abb7e","datavalue":{"value":{"entity-type":"item","numeric-id":505438,"id":"Q505438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c950086657cffe6ff785b873e96f6072490d4c8","datavalue":{"value":{"amount":"+0.796026885509491","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":"Q1811065$F8BD723C-5572-4E42-AB0F-38E9AF2A855A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Parameterized complexity of vertex colouring","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Parameterized_complexity_of_vertex_colouring"}}}}}