{"entities":{"Q2136878":{"pageid":2147621,"ns":120,"title":"Item:Q2136878","lastrevid":54317987,"modified":"2026-01-26T15:23:30Z","type":"item","id":"Q2136878","labels":{"en":{"language":"en","value":"An intractability result for the vertex 3-colourability problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7526491"}},"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":"Q2136878$1E7588DC-D8D0-4236-9D6D-537CB5DDFD92","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd6bdad7cca4af074f4e7cb9fca25f51c019f45e","datavalue":{"value":{"text":"An intractability result for the vertex 3-colourability problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2136878$05E6EEE8-3C1F-43AE-B68D-2858F8381759","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2536a5ae66cc5350a6003398fb75b6d8ffa449bf","datavalue":{"value":"1495.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$00E33B6F-1ED3-4CD8-A1F9-6DE42E26CD82","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e054a9ccf5815f88f803bc665fcea6e8237a1bc","datavalue":{"value":{"entity-type":"item","numeric-id":2136877,"id":"Q2136877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$BB9830CB-777B-4E16-AC27-8171D555E86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"31fa63c410743cfcc0d3d0fbbea5c808c23ab314","datavalue":{"value":{"entity-type":"item","numeric-id":1669582,"id":"Q1669582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$8AE4B733-D1AC-4D04-917A-C943133713F3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"34c0b92ce57892d31a862e7b55fbf1d57538b215","datavalue":{"value":{"entity-type":"item","numeric-id":156502,"id":"Q156502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$DC8DBF61-5E89-42FF-B81A-01F8B4C2AE0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cf2c65e2610039dd594d3eccc0f99fa0861d5c5f","datavalue":{"value":{"time":"+2022-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2136878$B8E396B1-299A-4C1C-9F85-A5F7484FF5D6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9248d4e0fc2b4efa524459a53577e54aa072cafc","datavalue":{"value":"In this paper, the vertex 3-colorability problem is considered in a very special graph class denoted by \\({\\mathcal{X}}_9^\\ast\\). It is the class of all graphs in which any 5 vertices induce a subgraph that is either a forest, a line graph, a kite, a dart, a banner (\\(P\\)-graph), \\(F_3+K_1\\), \\(W_4\\) or \\(C_5\\), where \\(F_n\\) (\\(W_n\\)) denotes the fan graph (wheel) on \\(n+1\\) vertices and \\(C_n\\) denotes the cycle on \\(n\\) vertices. It is proved that the vertex 3-colorability problem is NP-complete in \\({\\mathcal{X}}_9^\\ast\\). The authors use a translation in which they start with the 4-regular graph \\(G\\) and obtain a graph \\(G^\\ast\\in {\\mathcal{X}}_9^\\ast\\) in the following way: for any vertex \\(x \\in V(G)\\) with \\(N_G(x)=\\{x_1,x_2,x_3,x_4\\}\\) delete \\(x\\) and add edges \\(x_it_i\\) for any \\(i \\in \\{1,2,3,4\\}\\), where \\(t_1\\), \\(t_2\\), \\(t_3\\), \\(t_4\\) are four vertices of a graph \\(N\\) (called necklace) that has two properties: \\(\\chi(N)=3\\) and if \\(c:V(N) \\to \\{1,2,3\\}\\) is an optimal vertex coloring, then \\(c(t_1)=c(t_2)=c(t_3)=c(t_4)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2136878$BBE3BB71-6EB9-4D1D-A2A0-82D898B295B0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"512183e69be4ab0f9c803f93e55f4d9b77753376","datavalue":{"value":{"entity-type":"item","numeric-id":504963,"id":"Q504963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$90DC3D70-3743-4EDE-9660-A4893E2C82CD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$C70B7B27-BE6C-4FAA-AD96-DCE498D7BEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$67135D81-7ED7-4A01-B895-0DCF8C9D7240","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1aaaa45a467bff154cc206566a70704b90cde04","datavalue":{"value":"7526491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$5D491486-2A1F-4352-BF23-FB9C78293DFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2136878$D0210B0A-88B2-413F-8D4F-8C072ACEC870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03e54b0f5325e85d64a3313c26a35040a6c32825","datavalue":{"value":"vertex 3-coloring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2136878$B2269E6F-93B0-414C-BCFD-5F8E9D4D4506","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":"Q2136878$31473DC1-2A15-451B-8D28-E402F7CE736E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"263391b80feecabfaa7b8cc97f43b56de18a81c6","datavalue":{"value":"https://doi.org/10.1007/s11590-022-01859-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2136878$B4DED124-ACA4-4648-8E35-ADA31B872B52","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9a326b12146585929a31f460626bc8fd31cfbcbd","datavalue":{"value":"W4214736296","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$FDDBD4E8-D081-479A-878E-A3117F14CCA5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a0d346506465223f8a96355556be48c1ad0dfb","datavalue":{"value":{"entity-type":"item","numeric-id":1786047,"id":"Q1786047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$FE565B77-8AE8-4D8A-B902-9379F8D67C51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97d79f2a19c91cd2ba4fa37712ddbf5dc04117a2","datavalue":{"value":{"entity-type":"item","numeric-id":764301,"id":"Q764301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$3865DE35-75C4-45EA-9970-698221FB6253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f769489ebcd008167a2462b44af3c2449f3ca91c","datavalue":{"value":{"entity-type":"item","numeric-id":1146685,"id":"Q1146685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$96D4B24D-AF61-406D-86E2-86515C13E25F","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":"Q2136878$7CFBCEB3-121E-452E-960E-E25EC545ECB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7cf1cd878f46b9eeec5571ec20db3733fdf6b35","datavalue":{"value":{"entity-type":"item","numeric-id":1759872,"id":"Q1759872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$AEB2EAC3-18B1-4FF3-B191-E70CF7E871A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e544681d1cccccf6a64f441d01b39904ae77095","datavalue":{"value":{"entity-type":"item","numeric-id":476308,"id":"Q476308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$3E7EFE83-5D52-4E9C-A0EE-25B61329E279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e156e31cf1c03a94ee42319c5e653b95dcd615cf","datavalue":{"value":{"entity-type":"item","numeric-id":2978179,"id":"Q2978179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$BC7FB355-3952-42F9-878E-8602AEBCBD9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8266ed164b74ad24733ef85939db286920be08a","datavalue":{"value":{"entity-type":"item","numeric-id":344861,"id":"Q344861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$852AE2AF-0F5E-4CEF-8297-FF50885B0888","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"977cd433ecde040f39e4c4dde1c0b893e5757f3f","datavalue":{"value":{"entity-type":"item","numeric-id":848637,"id":"Q848637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$EE9FB8C2-07FB-4D4B-9839-A36761A8DAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47707362ea38a9307252d6fd07d68a2560b06ac8","datavalue":{"value":{"entity-type":"item","numeric-id":499486,"id":"Q499486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$F6EB3F20-41EE-447B-B90C-6C18512ACBBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55952e378589454474128d8823a63680494eab6c","datavalue":{"value":{"entity-type":"item","numeric-id":2352049,"id":"Q2352049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$E1635446-A6C5-4187-AEA6-F06FE0197037","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a4e7274bd9c2cbb220024510914f0648bf609ac","datavalue":{"value":{"entity-type":"item","numeric-id":2409536,"id":"Q2409536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$D7C7B699-8EF7-4126-97BF-65F092CE3B8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da53ccd2db6c6fca8f9e9581011e593de60a0893","datavalue":{"value":{"entity-type":"item","numeric-id":6143681,"id":"Q6143681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$DD9152FA-5B28-4C3E-8414-80E19BA72E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24b5aa1162e09a45b6485623c850d4b7aa30582f","datavalue":{"value":{"entity-type":"item","numeric-id":4973236,"id":"Q4973236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$664A18AB-E3D4-47D8-8C37-64D2C41493C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"35a44e11169a034de138802141ee5d73ec6d3d5a","datavalue":{"value":{"entity-type":"item","numeric-id":5236260,"id":"Q5236260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2136878$F3C1AE67-435F-4DB7-8B1D-7DDE9EBF4264","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"895473ee3dd9d4e656685ec55c80d4ec76a07cf2","datavalue":{"value":"10.1007/S11590-022-01859-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2136878$E02A54F9-0E9B-4EC9-8BE1-467D62738B66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04bc78aadfea7a2aa0176c822910b5ab64595469","datavalue":{"value":{"entity-type":"item","numeric-id":2409536,"id":"Q2409536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e56781daada00441eedad43f007788ffc3a5560","datavalue":{"value":{"amount":"+0.8808875679969788","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":"Q2136878$A2893FCD-4C15-4D4C-B489-1959519EA957","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a48d84e3c8b1cc46240d9ceff105ded5462171da","datavalue":{"value":{"entity-type":"item","numeric-id":2030141,"id":"Q2030141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58fd29062c7c3d611ca823e5bf8612d735f4f67c","datavalue":{"value":{"amount":"+0.8447225093841553","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":"Q2136878$E9188933-17FC-4ED5-9277-79437DBD1497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c39278d2d25e8e213c9cbe59f57d9fcb99337426","datavalue":{"value":{"entity-type":"item","numeric-id":4973236,"id":"Q4973236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00d7bf68c17f64cffe845ee3a1091b6feabd3d07","datavalue":{"value":{"amount":"+0.8441035747528076","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":"Q2136878$59847974-CDCA-478E-9D83-18DC2C713371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab48644a26befa445ec0014334c4cbcc254ee9b6","datavalue":{"value":{"entity-type":"item","numeric-id":2251141,"id":"Q2251141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13b9efe672f1c7b2c91956462d1c834905ee7392","datavalue":{"value":{"amount":"+0.840900182723999","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":"Q2136878$47B525E6-5878-471B-B749-6024A763D95A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64b83c964e67020a327e75e66a2f0cb8479726bf","datavalue":{"value":{"entity-type":"item","numeric-id":5755526,"id":"Q5755526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"16d4d0ef570ec10614a7a8bcc332c135208ebd56","datavalue":{"value":{"amount":"+0.8261600732803345","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":"Q2136878$25E7F344-E3A1-4DAC-B36D-40291BC4DDD9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2136878","badges":[]}}}}}