{"entities":{"Q1302157":{"pageid":1312907,"ns":120,"title":"Item:Q1302157","lastrevid":70101150,"modified":"2026-04-13T12:27:01Z","type":"item","id":"Q1302157","labels":{"en":{"language":"en","value":"Graph classes between parity and distance-hereditary graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1340636"}},"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":"Q1302157$D6D44175-053D-4CFC-82FB-24AE24D7EB0C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c3136d2bcde35e0a7a148541e01d4cb2e245c9c","datavalue":{"value":{"text":"Graph classes between parity and distance-hereditary graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1302157$54FD1045-F8FF-44F8-8852-A8CEF2E408A3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c245a327421987892fb0968e626772f2533a40a","datavalue":{"value":"0933.05144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$1D12904E-7108-4BA5-95B0-6A4097EEE6C2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a1230aa1685e8c2a33d61fca7b29d48165aebcdd","datavalue":{"value":"10.1016/S0166-218X(99)00075-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$D8B4BCB5-4D5D-4C2A-A1FA-EFF82A80123B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5254501b18649e16eeebf46a3730e555a1f783b4","datavalue":{"value":{"entity-type":"item","numeric-id":169276,"id":"Q169276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302157$31031C81-A3EF-4E5F-B692-CEB96F2893C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dde09a0944e88be3f96603714bb742e988212805","datavalue":{"value":{"entity-type":"item","numeric-id":169277,"id":"Q169277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302157$82ECFF57-8615-4BE2-8E2D-45FEA4C66943","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":"Q1302157$D80993E6-0C7C-4810-AC37-D8417102F14F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bc10aa9892b9c4f398ab8507090d5710329f3440","datavalue":{"value":{"time":"+2000-03-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1302157$7A0985B5-BC4F-445F-A8F9-A4C18317F6A4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c76bfb4fed45b43cac32fa87c9c427fa0fe08c52","datavalue":{"value":"We define operations \\(\\beta\\), \\(\\gamma\\) and \\(\\phi\\) as follows: Let \\(x\\) be a vertex of a graph \\(G\\) and let \\(y\\) be a vertex of a graph \\(H\\) such that \\(G=H-y\\). Then \\(H = \\beta(G,x)\\) if \\(x\\) and \\(y\\) are true twins (both vertices have the same closed neighbourhood in \\(H\\)), and \\(H = \\gamma(G,x)\\) if \\(x\\) and \\(y\\) are false twins (both vertices have the same open neighbourhood in \\(H\\)). Now let \\((X,Y,Z)\\) be a partition of the vertex set of \\(H\\) such that \\(G = H-Y\\). Then \\(H = \\phi(G,B,X)\\) if \\(X\\) is a set of false twins in \\(G\\) and \\(X\\) is contained in one color class of the bipartite graph \\(B = H-Z\\). Let \\(C\\) be a class of bipartite graphs closed under taking connected subgraphs. By \\(\\Phi_C\\) we denote the hull of \\(K_1\\) under the operations \\(\\beta\\), \\(\\gamma\\) and \\(\\phi\\), where \\(B \\in C\\). If \\(C\\) is the class of all bipartite graphs then \\(\\Phi_C\\) is the class of all parity graphs, and if \\(C = \\{K_2,K_1\\}\\) then \\(\\Phi_C\\) is the class of all distance hereditary graphs. In general, the classes \\(\\Phi_C\\), partially ordered by set inclusion, form a lattice of infinite height. Cunningham's split decomposition leads to characterizations of the \\(\\Phi_C\\) classes that enable polynomial time algorithms for recognition and isomorphism test.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$91FD271A-79E2-4388-B752-26CC1208FFDE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$CF1A81E8-B0E4-4FB3-91DC-F9DEBA55C0AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$1557BF3A-E280-4B91-839C-58C883C6BA52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$BC4AB4E2-5250-446F-B06E-B3564272AE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$587C275C-0AC2-45DE-80FB-5BA60B14277B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8b01891f5b8817d8ef91369c357914a7baa9474b","datavalue":{"value":"1340636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$9868254B-F8C5-4186-8C1E-2B6F3C9FACD8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25832dfa9e21272dfcd1a25394016e65412503ca","datavalue":{"value":"parity graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$5668F722-DCC3-4960-8241-93F37FBDA96D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358b2a890150a714c444c1162c9c5b41fa67317e","datavalue":{"value":"distance-hereditary graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$7A3BDEAC-A3DC-4958-9298-EE528CC3C9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dde62c1d9c84b346656546e8881b2406b933d488","datavalue":{"value":"split decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$F23C1F9B-086E-477D-AFD6-C0462C45D1AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$0FAAFC76-197A-4AD4-9B82-E7631E9D0BC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf16bbd4a05fdbd1b003839acc80b324384294c1","datavalue":{"value":"graph isomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302157$F0440260-7C2F-4AA6-AE91-C7CDA4459FE2","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":"Q1302157$6CB005BE-804E-4F9E-9922-858E67A8502C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b3bad7c8093087449970098a82b5f6e5cb8b3fbd","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00075-x","type":"string"},"datatype":"url"},"type":"statement","id":"Q1302157$78EDEE41-5D1B-473D-89F9-2FB63B5D5829","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"02b19cbf75ca83a69372ea2a1270b8ed9e1aba15","datavalue":{"value":"W1990144643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302157$C8AF788A-67E6-4385-B789-AB1649EAF75E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"432037ff17890432018f40f25d04575eff25ab4d","datavalue":{"value":{"entity-type":"item","numeric-id":4217589,"id":"Q4217589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a914eabc0336cc52ea7b440d70b1ba0a8e6ae01b","datavalue":{"value":{"amount":"+0.8609038591384888","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":"Q1302157$8892516F-4004-4491-BFB4-47C50396F3F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"692035e1c52e502f79bcc1c232dd642229af2838","datavalue":{"value":{"entity-type":"item","numeric-id":1302156,"id":"Q1302156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0421bc2e072adc79c73c51ce3fea21e05986a941","datavalue":{"value":{"amount":"+0.7793676257133484","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":"Q1302157$B5ED8E86-0E31-432E-A38E-8FA71DBBCE82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"294db6143777eb3a9bdef14f5f6812de92e329ae","datavalue":{"value":{"entity-type":"item","numeric-id":1932454,"id":"Q1932454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf560c0abb8851abb3b9072579928fb61ebc199f","datavalue":{"value":{"amount":"+0.7533318400382996","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":"Q1302157$5416A58E-4CBB-4435-8451-276B98A693A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee396aafba50c530fd089384ca3538b4587f05b4","datavalue":{"value":{"entity-type":"item","numeric-id":3222874,"id":"Q3222874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a70d521ecaae8dbb436881221bf54a6ea3e7dc1","datavalue":{"value":{"amount":"+0.7499371767044067","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":"Q1302157$025BC577-669E-493D-B40E-AFA3DE51CFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"980796144e6d4d3d1a66813ff0c75a027ea25847","datavalue":{"value":{"entity-type":"item","numeric-id":3010409,"id":"Q3010409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f893331e0ad222abdf827ca436d42157505f800a","datavalue":{"value":{"amount":"+0.7418458461761475","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":"Q1302157$0474E39E-46F9-4004-9961-7B2B71F63D50","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph classes between parity and distance-hereditary graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_classes_between_parity_and_distance-hereditary_graphs"}}}}}