{"entities":{"Q1197003":{"pageid":1207752,"ns":120,"title":"Item:Q1197003","lastrevid":66338538,"modified":"2026-04-12T09:26:01Z","type":"item","id":"Q1197003","labels":{"en":{"language":"en","value":"Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 89879"}},"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":"Q1197003$701B9AAE-75C6-4259-9F7B-A9C2EEB0DF8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b3126d081e112a72a0dd07b9c8300077cff46d49","datavalue":{"value":{"text":"Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197003$83EFBE1A-DC69-485D-9F3F-0536027096CC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"56381c6384b6bd7150681c33e83c1878e873ae37","datavalue":{"value":"0783.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$0C001559-F648-4912-993B-6C78A4198FE1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bfbb892a019c9ae6320a593100b95944915c02be","datavalue":{"value":"10.1016/0012-365X(92)90623-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$73C890F1-72AD-4072-9BC0-6C05E970032D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5b17683dd2eedd3f1d821a1087aa218b2b31d17","datavalue":{"value":{"entity-type":"item","numeric-id":1160451,"id":"Q1160451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$378FF534-D04C-4D79-B330-8681F52047D4","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":"Q1197003$9EFA1997-8470-43C7-B089-07A40E0AC9DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-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":"Q1197003$0491581A-F277-4555-AB17-2FB965A72E30","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4aa31d0fdb41a65c0cf7335294b854e1b49cebd0","datavalue":{"value":"[For Part II see ibid. 110, No. 1-3, 81-118 (1992; Zbl 0774.05064).]   A graph \\(G\\) is perfect if for every vertex-induced subgraph \\(H\\) of \\(G\\), the largest clique size of \\(H\\) equals the chromatic number of \\(H\\). Berge has conjectured---the Strong Perfect Graph Conjecture---that a graph is perfect if and only if the graph and its complement contain no odd-length chordless circuits other than triangles. A (0,1) matrix is linear if it does not contain a 2-by-2 submatrix of all ones. This paper studies graphs whose vertex-clique incidence matrix is linear. Such graphs are characterized by the property that they contain no induced subgraph isomorphic to \\(K_ 4-e\\), a complete graph on 4 vertices with on edge removed. This paper presents a new matrix-based proof of the Strong Perfect Graph Conjecture for \\((K_ 4-e)\\)-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$EAA3F961-BB92-48BE-B539-A0F19AADB163","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$A45CA446-87F2-4302-A1C6-E7E271B32A3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$27A6480B-9C93-40DD-967E-24E1E3EC37E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"772466e23f65811e4792a58a12ff09d79c338e5f","datavalue":{"value":"05B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$1417B61C-039C-4270-80F8-65A12CB56EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"98259a5dd4d8db83a95d10edc3bf87986357d020","datavalue":{"value":"05E30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$7EFC1153-1C54-427D-96D8-CAED348F2EEE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"eca56f0c6c899ed03b4bb20ae96cd1f3ee381076","datavalue":{"value":"89879","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$94892A9F-F438-463C-AD4F-73825ED716AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a71aa20106eb02b6185c977a24af2dc319e4157c","datavalue":{"value":"linear perfect matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$58243F97-5457-4769-BC6C-EB84D460A802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44563c78d4f2138cb8b818570d17e585e9a6fdf1","datavalue":{"value":"star cutsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$D4732914-F509-400E-8EC3-7AD381CD8EDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$FB1A0B08-25D7-4907-92B5-30491C8F3EF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ffa0b0ba339eea1c6730a3ce027ea7878c1495d","datavalue":{"value":"clique size","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$866FCB53-9F0B-4A21-BF74-81BF7F7247B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$70DEF657-6708-42FE-9359-0BDA1F368BA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"262bdfa8edfe99210fd9b6503f70cfab463acd03","datavalue":{"value":"incidence matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197003$61E5BE49-F967-4E77-9F34-803072626EE0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1036338e57ff468c07842b36de9d1ae094bc8bd2","datavalue":{"value":{"entity-type":"item","numeric-id":1110542,"id":"Q1110542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$46719CCC-814A-47DD-97A1-68B95FADE62C","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":"Q1197003$DD398564-D3E6-45D9-8BA2-0834EE9048B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$49F409F8-9B68-42E4-A3F8-C9BAC60B6D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$0CE8A191-AD71-4246-8616-D42D3F1DC880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aac1201a7f1d85b811c912447210e3e85e29333","datavalue":{"value":{"entity-type":"item","numeric-id":3222223,"id":"Q3222223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$CFC4E0E7-CE63-45B2-9EC6-A926B6250D07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8439cd84a49b5225dfa76205f17bb5321104a88b","datavalue":{"value":{"entity-type":"item","numeric-id":3222886,"id":"Q3222886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$E452C036-1310-4105-AB6F-A700787D1EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$66132FA7-342B-4563-8BD7-93F26533932E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"377fc7d6f0f87cd999526d782ba240d822d49abd","datavalue":{"value":{"entity-type":"item","numeric-id":1121289,"id":"Q1121289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$C78CAD3B-D66D-4DA6-AE11-690BB9EFB065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4af1dfbef55e5c6f877defc758d39f47fcfc762b","datavalue":{"value":{"entity-type":"item","numeric-id":1118619,"id":"Q1118619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$9E39C2DE-415E-4144-ABE9-388580DEFB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2944fad23a9da4bdb6224aa0cc98656216bb9c6b","datavalue":{"value":{"entity-type":"item","numeric-id":3783863,"id":"Q3783863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$A2E12008-9977-411F-B5C4-76A1924631BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8eb89a00a3eda92ea9ddeab1a99ec3e65d6f1d0d","datavalue":{"value":{"entity-type":"item","numeric-id":1823869,"id":"Q1823869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$331AB271-46C9-46C4-A59C-7C5166E5C260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c183b5a6f932d005dd20d44ce907e93d62bf7a89","datavalue":{"value":{"entity-type":"item","numeric-id":1196165,"id":"Q1196165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$0E0CB716-0E7C-4CB7-A9D3-97EDA25F795E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"108ba7bf49c0395fea1fae77e724d1c7526e8cf5","datavalue":{"value":{"entity-type":"item","numeric-id":1194854,"id":"Q1194854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$A8039C2D-895D-4C3F-B7E4-BAC93EAFE6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"247905ed263e19dd1256e27ec3f22ab7443ca318","datavalue":{"value":{"entity-type":"item","numeric-id":689142,"id":"Q689142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$D03008C5-12BC-45E7-BDFD-F0BBF7375CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d16545e9f886cc1aaeee9edfe775f0f02f55730a","datavalue":{"value":{"entity-type":"item","numeric-id":2266722,"id":"Q2266722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$7C67975D-21CD-43E7-8696-326B703C02DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8b5a3797dc7a026e6a2fc4c672460d95d97584d","datavalue":{"value":{"entity-type":"item","numeric-id":5685113,"id":"Q5685113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$7C6BCDC8-5D5C-4BB5-A8E3-AA5379232AD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddbe097f62791bcc42fe71dd30e6b393e0a8c6f9","datavalue":{"value":{"entity-type":"item","numeric-id":2553445,"id":"Q2553445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$E6EC9F15-C4CF-4207-BFAC-A81BE2954813","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11c607b0c6f7409cf390c5742731d5c7cfd460f5","datavalue":{"value":{"entity-type":"item","numeric-id":4770779,"id":"Q4770779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$C00AED4C-2F15-4E61-AF23-ABB37289A748","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46cea1204e8b56e8cdf89cf3b32e1a95f1f87fb2","datavalue":{"value":{"entity-type":"item","numeric-id":1213881,"id":"Q1213881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$A7757436-84A2-4F2D-9AD3-B85F5BBE1E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cceb1234cc3145b85555d80daa70c1ec324e91e6","datavalue":{"value":{"entity-type":"item","numeric-id":5663885,"id":"Q5663885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$04285FDF-3827-4A60-8182-FDE60E8401CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3684641a14441fb3cb248e9a7267fb00b10c9316","datavalue":{"value":{"entity-type":"item","numeric-id":4173373,"id":"Q4173373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$112F9127-D0A0-4C8B-BA13-272A2562F88D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b9b8eafd1b87c89b391a5a966c0dde6e01b96f","datavalue":{"value":{"entity-type":"item","numeric-id":1149784,"id":"Q1149784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$365761C2-A094-4455-A8C3-F9FE5062003C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b084fd23a4e64f5f3680a8f9c0c45f2c9f039cfb","datavalue":{"value":{"entity-type":"item","numeric-id":3680604,"id":"Q3680604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197003$236EECBF-8086-4D23-868E-A2618998CBB6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ab7979989e82ab9520dd179626413f89b26b754b","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90623-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q1197003$0EB6FB17-0463-4E01-BF62-DC466FBF1144","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"52d67db9557843f1c5eca1d39128bbdc39fa8da7","datavalue":{"value":"W2048487659","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197003$5C54E4FF-16FD-4BE3-81E0-1757EA4A79C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"630e54c7fa45d42d2c208689f0ac8600b3b95f15","datavalue":{"value":{"entity-type":"item","numeric-id":4731202,"id":"Q4731202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"619514210b5c601dd28922f4540d6e97225d9b43","datavalue":{"value":{"amount":"+0.8697748184204102","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":"Q1197003$C2866320-2E37-493C-80E7-4B90F49397CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"892eafb07e69706c0f9e30bd9a85059cda0c982e","datavalue":{"value":{"entity-type":"item","numeric-id":1403295,"id":"Q1403295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deceb924dda4622db257ef35dd58e078b70401f7","datavalue":{"value":{"amount":"+0.847541093826294","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":"Q1197003$CFAB112E-C79C-4936-81A6-56BC2E0AB70F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce033e0111a16eec10eb515c8e24ea0bf95b8761","datavalue":{"value":{"entity-type":"item","numeric-id":1334944,"id":"Q1334944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deceb924dda4622db257ef35dd58e078b70401f7","datavalue":{"value":{"amount":"+0.847541093826294","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":"Q1197003$E64F845C-85B2-4E51-8803-6DBA7CD27830","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc20b62cb9c6b85fbe0b1784833623ce37018561","datavalue":{"value":{"entity-type":"item","numeric-id":5903942,"id":"Q5903942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cbed932f09d2320ccfdd6ad10035a55e1aa6a1d","datavalue":{"value":{"amount":"+0.8471549153327942","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":"Q1197003$7DF3C57C-FDE6-4F76-ACB9-D85357103F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0219261c33170d756b149ce0319bf5824298aeaf","datavalue":{"value":{"entity-type":"item","numeric-id":855256,"id":"Q855256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4aacf31eb037858ff940fd04c4188b45e295b446","datavalue":{"value":{"amount":"+0.8471211194992065","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":"Q1197003$25127EC6-884A-4166-BB51-076C6D73ECD0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Articulation sets in linear perfect matrices. I: Forbidden configurations and star cutsets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Articulation_sets_in_linear_perfect_matrices._I:_Forbidden_configurations_and_star_cutsets"}}}}}