{"entities":{"Q801935":{"pageid":803783,"ns":120,"title":"Item:Q801935","lastrevid":42702495,"modified":"2025-07-08T15:58:47Z","type":"item","id":"Q801935","labels":{"en":{"language":"en","value":"Some undecidable problems involving the edge-coloring and vertex-coloring of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3880755"}},"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":"Q801935$78D6CFAE-ADA1-45A4-B6A0-7DEA6ED34B74","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fd0403f0936a5828b4f34d5b06854f0192d11444","datavalue":{"value":{"text":"Some undecidable problems involving the edge-coloring and vertex-coloring of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q801935$CADB6204-093A-4266-9D24-C9D94BF43A3B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"832485f721ad48218b59a23dd822f725c29cbd6c","datavalue":{"value":"0553.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$E1AFD3ED-0883-4D1D-84E2-8005FDD7D5AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bbc39615c36b99ad867fcec33479d21b493cd05f","datavalue":{"value":"10.1016/0012-365X(84)90046-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$D5702BFF-F37F-4F44-A01B-A130251F30EC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce4aee54645fb34a947a8e72345e94b43fefa3e4","datavalue":{"value":{"entity-type":"item","numeric-id":801934,"id":"Q801934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$709CB48B-DD7C-4BD6-9B50-BD3FB8E546A9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$B48C3142-1B93-4D5A-9E1E-027A82A87FDC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q801935$295C5BEF-D3BE-4956-8DCE-9448655362E2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bfbe2cc2e9f69ebb05073a3f8da90ec1bb15112b","datavalue":{"value":"In Ramsey theory for graphs the following statement is of relevance: \\(''F\\to (G_ 1G_ 2)''\\) meaning that there is a 2-coloring of the edges of the graph F such that no \\(G_ i\\)-subgraph is monochromatic in color i. It is well known that deciding \\(F\\to (G_ 1,G_ 2)\\) is an NP- complete problem. It is natural to investigate related decision problems for finite graphs \\(G_ 1,G_ 2\\) and infinite graphs F.    Theorem: Let \\(G_ 1,G_ 2\\) be either \\(K_ 3\\) or 3-connected. Then an infinite graph F may be constructed such that \\(F'\\to (G_ 1,G_ 2)\\) is undecidable for the class of all graphs F' obtained from F by adding finitely many vertices and edges.    Moreover F may be chosen to be ''doubly-periodic'' and thus a finitary object. The theorem follows from the undecidability of the extension problem of 2-colorings of finite subsets of edges of F without i-colored \\(G_ i\\). - Analogous results hold for vertex colorings with at least 3 colors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q801935$C9F68B83-49EC-42F5-A1FA-EFFF627E0E1D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$4FD82DAE-AC1E-45BC-9BEA-0AFCB9F035B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"407654cf92f0702e03297e7fe541e25fa3f13c2d","datavalue":{"value":"03B25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$D236A03A-8891-4EA2-9C90-D9248875F616","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3498bed6de4599f264e78f4e6b39467c01b9dfb8","datavalue":{"value":"3880755","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$4EFF2CD0-17EE-4E62-97A9-8D7AE2E2140F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea33b309306e49b597817f466193bd42e7d9d48d","datavalue":{"value":"Ramsey graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q801935$73628B95-3C1B-4A13-B5B5-8C1656BA33CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q801935$79BDE376-367F-4B88-AE62-748FADFF4F59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"318e95d2cea290f1765c519973e59af6e6b8d5b3","datavalue":{"value":"vertex colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q801935$BE41E4B3-46C5-4596-9A01-9B8DC1033601","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":"Q801935$60BA9AE0-DDCC-4853-A0EB-09AB1F78A21F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3e0bf6d66ae7c4b6b46e88d6d5b96072d8e8fa","datavalue":{"value":{"entity-type":"item","numeric-id":5597521,"id":"Q5597521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$B3992023-21BC-44E6-A68A-88D83857E4EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d04898e97bf3ec7cb5cc3085911954188e5a76cb","datavalue":{"value":{"entity-type":"item","numeric-id":3937444,"id":"Q3937444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$D81D17A1-B87F-4A84-B55F-74238DC55F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea7bf83fe535989504f79a718b97c350ec04a854","datavalue":{"value":{"entity-type":"item","numeric-id":3201758,"id":"Q3201758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$F3994957-16E6-4DB1-809E-AD212EF76331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81e3b7a8316062a8862a42d30fa611f2626d8db1","datavalue":{"value":{"entity-type":"item","numeric-id":4745271,"id":"Q4745271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$4EF03BFA-4E38-4575-B623-3AD8B86DB038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a26d9d09fff9d8eaa0e1265db5f3a57066a47783","datavalue":{"value":{"entity-type":"item","numeric-id":1057876,"id":"Q1057876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$4E5B9305-6B85-4187-9300-809B33939645","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":"Q801935$3D3C59FE-7C10-4EFD-814E-4BF02EC5F0BF","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":"Q801935$E4733551-8B81-4E25-96B8-1D8945B3D3DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f47f7850801654ea9993f2f197d1fde75c0c53d","datavalue":{"value":{"entity-type":"item","numeric-id":4175305,"id":"Q4175305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q801935$B70ADE2C-E276-482A-92B0-F9E100C8A959","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"23ac75de0cc05f211da0c6ce5b0f6ccdd4d2eaf0","datavalue":{"value":"https://doi.org/10.1016/0012-365x(84)90046-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q801935$7DFB8EF1-A9E5-4E95-8B15-71386D0CE88C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a4c084843481d4feb51ffa603aeb21d79ce26995","datavalue":{"value":"W2081035511","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q801935$C8F65516-0B82-49C1-B16A-34CA6678FD9E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb950d210c5e21655e19ca87c15886f6e3076d1e","datavalue":{"value":{"entity-type":"item","numeric-id":4241100,"id":"Q4241100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1b21ae8635edddfaac6335040558ac10fd52378","datavalue":{"value":{"amount":"+0.91384625","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$DD144EC3-5074-414F-B1CE-16E59F7ECFCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63d4c3f38e2b204c6a7f08ebbfe93d1bc4fa29cd","datavalue":{"value":{"entity-type":"item","numeric-id":2822602,"id":"Q2822602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"765a3cc029001eb9fdb90c0daf8fd97c0a0b44f0","datavalue":{"value":{"amount":"+0.9042718","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$76574F1E-4D07-467C-B41A-6973457FCC23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"022384d4e8d7d7a7a19c908ca1d5f6c7b8555952","datavalue":{"value":{"entity-type":"item","numeric-id":2712481,"id":"Q2712481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5ddc3fd70adcbf58a3246533d537ccc7a1e12828","datavalue":{"value":{"amount":"+0.90139246","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$AA47E22D-7B77-412D-BCD7-32CDFC362049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"025f6392089168878605a7a7a0c0708af2ed91cb","datavalue":{"value":{"entity-type":"item","numeric-id":3983109,"id":"Q3983109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66e6e5e893d4e8a81a93a45f8129342bd2520336","datavalue":{"value":{"amount":"+0.8993707","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$4BA99EE5-5B96-404D-87E7-126A3622141F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"574a8133b285fd4cebbcb58577a3319db5a4680a","datavalue":{"value":{"entity-type":"item","numeric-id":5251969,"id":"Q5251969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fac50a711427b2a261bf70b0480393b5a5ed63c","datavalue":{"value":{"amount":"+0.8985579","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$C70F292B-0CAA-4513-ADCF-A182618A4903","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f977b87df8192fb415504358af3e9c1ac2277a84","datavalue":{"value":{"entity-type":"item","numeric-id":5143707,"id":"Q5143707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"754715029747cd981f9a9c2091afeb68e8c4ca9e","datavalue":{"value":{"amount":"+0.89550537","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$62342709-2A4F-4CEA-86AF-0AD78FD450C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2e174b44e9cfe010cf5440f3b72481484a9d9a5","datavalue":{"value":{"entity-type":"item","numeric-id":1022440,"id":"Q1022440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4e5427c136a899a3fbaf211777b28a4814b5c9a","datavalue":{"value":{"amount":"+0.89382917","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$D2000BB4-05F2-4C85-B952-FFDB84FC49A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f367cb1fcedab1d6ba15b821369bcec91e92a749","datavalue":{"value":{"entity-type":"item","numeric-id":5167097,"id":"Q5167097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83e7cf8537cadd174a97f2e03b1bc41f009be5a8","datavalue":{"value":{"amount":"+0.89337975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$812741B6-8204-472C-8FDC-AD3AC7BA9BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f12010688bd193b004fd77e8537984e8a36d021d","datavalue":{"value":{"entity-type":"item","numeric-id":2924252,"id":"Q2924252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d864d02e84a9f30030572789af0ddfa0eeb1d8e5","datavalue":{"value":{"amount":"+0.8932564","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$0C639722-BAAE-45F9-A39B-7E1110962487","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4e8fa4e0fe1c737ec8d2fca38e63a4562722a7","datavalue":{"value":{"entity-type":"item","numeric-id":3735724,"id":"Q3735724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e9201aa95cf12823243151005278e8637609386","datavalue":{"value":{"amount":"+0.892957","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q801935$352F7950-1FF7-4DA6-AA48-1809E9662674","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:801935","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:801935"}}}}}