{"entities":{"Q2848741":{"pageid":2859461,"ns":120,"title":"Item:Q2848741","lastrevid":79757828,"modified":"2026-05-06T14:38:39Z","type":"item","id":"Q2848741","labels":{"en":{"language":"en","value":"The hardness of the functional orientation 2-color problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6212190"}},"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":"Q2848741$4F77EC9D-30EC-43E3-980C-E1052C47C298","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2455fca0431a31af10c4076deb36c8f2225e5162","datavalue":{"value":"1278.68102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$838750B7-1AD4-4645-AD4E-C2B83202BFD6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae0a3dbcc85f7772a68a99cd01ec2d877c3444ff","datavalue":{"value":{"entity-type":"item","numeric-id":2848740,"id":"Q2848740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848741$B2B2C349-7064-4D36-A86F-24E52C35D60C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b17c7f12658e357d524934c6c0324f832fd962b1","datavalue":{"value":{"entity-type":"item","numeric-id":2077382,"id":"Q2077382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848741$2075CDC4-ED98-422C-87EB-10677D708356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3d81d9de4719ede5e83d0afad90fb6c5468229ee","datavalue":{"value":{"entity-type":"item","numeric-id":442238,"id":"Q442238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848741$CA8C71F7-7F05-4962-84AC-9116B61EF5EA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"43e878d8f753446abefa1b1ceb0637b91afae47a","datavalue":{"value":{"time":"+2013-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2848741$414F9714-FBC5-4023-871B-B25A1940CF4B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c969337464b6671c8fa61b264dfe899ebf568b58","datavalue":{"value":"https://arxiv.org/abs/1210.2544","type":"string"},"datatype":"url"},"type":"statement","id":"Q2848741$37ED9508-321F-4BEC-90B9-C9E91E911370","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$06FAE3FC-8006-44DF-A663-7299F92C256C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$BF261034-4A25-4110-BCE1-91C10632C151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$03CD3196-C4FB-417A-B2F9-5C54EEB11AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$7401C3CC-1E6A-4446-BE70-9DE3BBB772F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$77C0BFD4-BAC8-4A6C-BA6E-A342F75B6CD1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d1450fe658beef662201c333db62f502e4a2c47c","datavalue":{"value":"6212190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2848741$1652AFA7-0BB4-4D90-89D6-C3481E524B43","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33d2947596393a86baf5284a3c5ca0f996484ef1","datavalue":{"value":"functional orientation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848741$D7D70E1B-5FF6-41A8-B061-1F7BE88CA872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20a9087604298d05b19099abe36de4380b5be4d2","datavalue":{"value":"2-color problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848741$6B737540-EAAA-4EE5-9B98-6E82B90A7514","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":"Q2848741$D75DD9D3-B56A-452D-AE72-CB17693400EA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"619e954bc1bb9c5e683d0c2d5b3c4764e8de7cbd","datavalue":{"value":{"text":"The hardness of the functional orientation 2-color problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2848741$237C409C-40BB-41FF-8856-08EDA4101A56","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4475e942e511a8e1762a91638eb522e6040025ba","datavalue":{"value":{"entity-type":"item","numeric-id":6562416,"id":"Q6562416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848741$572A5D90-D9BE-456A-9BE2-A5ED1730D978","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ff565300372d52e1930d8bc8c093ec7a295b3004","datavalue":{"value":"A functional orientation of a graph is a function \\(f\\) from the vertex set to itself such that each vertex \\(u\\) is adjacent to \\(v = f(u)\\). The name arises from assigning a direction on the edge \\(uv\\): each vertex then has exactly one edge directed outwards. Functional orientations occur in applications such as finite-state machines, the analysis of algorithms, and hash functions.NEWLINENEWLINEThe functional orientation 2-color problem is to determine when a graph has a vertex 2-coloring and a functional orientation \\(f\\) such that any edge \\(uv\\) joining two vertices of the same color has either \\(f(u) = v\\) or \\(f(v) = u\\). This problem is known to be NP-complete for planar graphs of maximum degree at least ten, but is polynomial-time solvable for planar graphs of maximum degree three.NEWLINENEWLINEThe authors show that this problem is solvable in linear time for planar graphs of maximum degree five and is NP-complete for planar graphs of maximum degree six.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2848741$81FDB488-E5ED-4B50-B99A-A667653CCCD8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2848741$D793A834-349E-4743-98B5-1243DD606438","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ae76b706935bd7e0522596726e2ec67342ff7d2","datavalue":{"value":{"entity-type":"item","numeric-id":897592,"id":"Q897592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15e364cdd991ec6555f1e036e1fc4e379adc74ea","datavalue":{"value":{"amount":"+0.7893573045730591","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":"Q2848741$A86862C2-62C5-4BA4-9380-FE52EF793269","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f74863cb0059daed8ae5dc26d9a7b5f91f214d83","datavalue":{"value":{"entity-type":"item","numeric-id":5897986,"id":"Q5897986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5d47a9dfa9996a1d6cdaca64271a21b368dd8ce","datavalue":{"value":{"amount":"+0.782531201839447","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":"Q2848741$817E0587-F9F2-4F82-A035-0060F7863A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c9e74afa5735674b6bd3a5a118ccfcd4ba4529d","datavalue":{"value":{"entity-type":"item","numeric-id":2445254,"id":"Q2445254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7083044ded9a9cc68cf95e54b810e2c73981328a","datavalue":{"value":{"amount":"+0.7813270688056946","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":"Q2848741$4D13BB98-1681-4DBB-A75E-163C9D748790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86233ec7705251d7c7705ce6239d48ff3f1081e1","datavalue":{"value":{"entity-type":"item","numeric-id":489364,"id":"Q489364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d2a1a73997d7f5c221a97e61c7d40cc0dee9bcac","datavalue":{"value":{"amount":"+0.7720646262168884","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":"Q2848741$28309F07-3161-4AF9-8D44-905D42CCA90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3f166cb0cb4be9c2dcaebf291d22b755323ffed","datavalue":{"value":{"entity-type":"item","numeric-id":1891685,"id":"Q1891685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f0e93d321e67048a766210315eefb6b2dfa5fe7","datavalue":{"value":{"amount":"+0.7717103362083435","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":"Q2848741$E7DDD67F-7FCF-4EC3-A551-53D914ADF1C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The hardness of the functional orientation 2-color problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_hardness_of_the_functional_orientation_2-color_problem"}}}}}