{"entities":{"Q1598796":{"pageid":1609536,"ns":120,"title":"Item:Q1598796","lastrevid":67954482,"modified":"2026-04-12T20:27:52Z","type":"item","id":"Q1598796","labels":{"en":{"language":"en","value":"Forbidden subgraph decomposition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1746235"}},"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":"Q1598796$8F05A08E-0495-44F3-9E27-78848F9D8BF9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e543a8e0d2ebe779c360d57c297f6a13e9cb9fd","datavalue":{"value":{"text":"Forbidden subgraph decomposition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1598796$A001373B-A841-4620-911A-6B9101DEA7E9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba77ffe8b1b8661e9494cb498af71d84d0a12455","datavalue":{"value":"0994.05122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598796$C680AC4E-E900-4AA7-90B9-0EAD0610FEFE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6fdb0fd41db9c04961e78a07c4c25307356a26c0","datavalue":{"value":"10.1016/S0012-365X(01)00173-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598796$FFC8CB66-EE18-482B-AF4A-FDF90DA75DE6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3d173afbda7d364ee20fa0af1c6602b56374da2","datavalue":{"value":{"entity-type":"item","numeric-id":187141,"id":"Q187141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598796$B06641B7-2E5F-4DA4-80E6-47FB6148A303","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0ef8392e01c11e85b032ddf62d87088b822bd19a","datavalue":{"value":{"entity-type":"item","numeric-id":344852,"id":"Q344852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598796$FC5345CF-EC73-408A-8644-44C8073F622F","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":"Q1598796$6994D3B1-7177-44A1-9592-FB6BDA8DCCF8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"948d99aa5eeeabdcba9b276ed31f146b3beac4cb","datavalue":{"value":{"time":"+2002-05-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1598796$7D55454D-5645-4CBC-9BBE-B437AEBDB349","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bd9a766a1e1e5eb0c9f065402f85fc0ccba8aece","datavalue":{"value":"Let \\(F=(X,Y)\\) be a bipartite graph with bipartite sets \\(X\\) and \\(Y\\). Given a graph \\(G=(V,E)\\) and a partitition \\(P = V_1 \\cup V_2\\) of its vertices, let \\(G_P = (V,E*)\\) be the graph with edges consisting of all those edges in \\(G\\) with one vertex in \\(V_1\\) and the other in \\(V_2\\). We say \\(F\\) is tidily induced in \\(G_P\\) if there exists an isomorphism \\(f\\) from \\(F\\) to an induced subgraph \\(H\\) of \\(G_P\\) so that \\(f(x) \\in V_1\\) for all \\(x \\in X\\) and \\(f(y) \\in V_2\\) for all \\(y \\in Y\\). We say \\(P\\) is an \\(F\\)-free decomposition of \\(G\\) if \\(|V_1|\\geq |X|\\), \\(|V_2|\\geq |Y|\\) and \\(F\\) is not tidily induced in \\(G_P\\). The authors study the complexity of recognising \\(F\\)-free decompositions for small \\(F\\), in particular bipartite graphs with at most 4 vertices. The main result is that deciding whether a graph has a \\(2K_2\\)-free decomposition is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598796$FD23FBE1-D0FA-4CEB-9481-F0B14278D6A8","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"499ad4e5adce4e7df75a6d2718bb76044fcca478","datavalue":{"value":{"entity-type":"item","numeric-id":184654,"id":"Q184654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1598796$41DF4E6B-38E4-417A-BBEE-9E14D223A6FA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598796$6F738656-3A6D-4B00-940C-56637A918DFC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9df453ceaaed44cd0202b64b7bc7ea45cb968ac6","datavalue":{"value":"1746235","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598796$44E453BA-F686-4ECB-8592-690E16B3C14D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598796$D6ABBD55-6D8B-469C-A022-4D6344308078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598796$F3C0AEEC-2AC7-4E50-8B1E-30BBCBE625FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1598796$E5E6BD8A-3E5D-43E6-BB84-1BA58CB84E72","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":"Q1598796$F88A05E6-B50D-42E4-A0DC-F804C7F699F2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f52b3f667b52a6b85db62398d0abe1781f7f12f7","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00173-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1598796$95B335CB-127E-4241-B71F-95592C5E4B23","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"032611fafbe0320615f0d874576405ef0166335f","datavalue":{"value":"W2017867718","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1598796$A89D2F6F-BA8B-4113-BB24-A4AE8D104574","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ebfcec3f33455d95d5d118f1d4cdafdaf19c771","datavalue":{"value":{"entity-type":"item","numeric-id":3781793,"id":"Q3781793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a96598fb75af07c65778065b355a723379c964ac","datavalue":{"value":{"amount":"+0.9789517","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$4AABDAB3-40AC-409D-90B8-43EC9CD2D516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08063802539abfd8fc872e111eba1009783024f6","datavalue":{"value":{"entity-type":"item","numeric-id":2758062,"id":"Q2758062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e74cb0134642b8f68714c9ca6650a86400fa7b2b","datavalue":{"value":{"amount":"+0.9326328","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$DA19874C-8CC1-4E8F-B4B6-E62BC5340A3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9e9eac545cfe13706329158703e879b36c1b9a4","datavalue":{"value":{"entity-type":"item","numeric-id":2413330,"id":"Q2413330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"010e63b9a59670a1508c3c1d951cb833490ad692","datavalue":{"value":{"amount":"+0.9203098","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$31DB8734-F24B-42FF-9794-7FE5E0CC2D45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04d7c906d3b4db6351fda75c87fc551643f49441","datavalue":{"value":{"entity-type":"item","numeric-id":1884919,"id":"Q1884919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53c857084b8fc60611a1b7abe99e6282394c70aa","datavalue":{"value":{"amount":"+0.9191774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$98FC8895-7CBC-42A3-9EA4-551614FD6449","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1398f4cdbad713298b5e606d57b67b5b7053acfe","datavalue":{"value":{"entity-type":"item","numeric-id":3826590,"id":"Q3826590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4247c5891a271491e9861486993f538ae73e2a34","datavalue":{"value":{"amount":"+0.9130411","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$53693C37-BF14-4DDB-B1A3-114ED3638FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1318e6253dd2ee5c2a1fcfc897da2039f9f7e3bb","datavalue":{"value":{"entity-type":"item","numeric-id":2666586,"id":"Q2666586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cd37db528d7c8ead6b6cea4038f171220c69fb9","datavalue":{"value":{"amount":"+0.90551484","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$AFD457BD-6AB7-4D02-875A-EBE1CD852AB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bea083e1623c6649a814510eead5e2f43735995d","datavalue":{"value":{"entity-type":"item","numeric-id":3971999,"id":"Q3971999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e8e667ac5cf3b9ace7dfdc006d7ede03f4dc90f","datavalue":{"value":{"amount":"+0.902906","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$B5A7EAED-496A-467D-BE04-586E1301FA67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92ab1bea8b3795b37c52e5eb3b9011b4a144da42","datavalue":{"value":{"entity-type":"item","numeric-id":4326211,"id":"Q4326211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65184240c983c6231ad6f799727c65e691a64ec2","datavalue":{"value":{"amount":"+0.9023385","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$636D3E23-5AC8-42A2-89FE-3EABACDEDFAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"116f93f57cff411d64d7b80f6a871a527935c9dd","datavalue":{"value":{"entity-type":"item","numeric-id":3838206,"id":"Q3838206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d14a273edb274a715c247c7a2c14e281e708c16a","datavalue":{"value":{"amount":"+0.8947122","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$3CF68020-04DD-473C-91DB-A747E8EC0266","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1cb3ff863e20a0674dfd21c8f0b7452fb41122f","datavalue":{"value":{"entity-type":"item","numeric-id":2040001,"id":"Q2040001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a98cdebbfc434a4acefa8d140e2238bb9381f64","datavalue":{"value":{"amount":"+0.891745","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1598796$7FA538B0-D9A6-4762-A6DC-C4FCAF45AA41","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Forbidden subgraph decomposition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Forbidden_subgraph_decomposition"}}}}}