{"entities":{"Q1306428":{"pageid":1317178,"ns":120,"title":"Item:Q1306428","lastrevid":81223244,"modified":"2026-05-06T18:01:25Z","type":"item","id":"Q1306428","labels":{"en":{"language":"en","value":"A description of claw-free perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1347242"}},"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":"Q1306428$95A1F340-9679-472A-9989-848F680155E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"48b04244cf5b478ebdf81310f8b98ac29ce17c13","datavalue":{"value":{"text":"A description of claw-free perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1306428$0CEB304E-1374-461B-BDA8-728FF6197CBB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"caef431e7363d0816a304ec06ddcd15824907ac2","datavalue":{"value":"0933.05062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$C6E90854-EAFD-4242-8841-260703C01E1C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2d7eb4aa6a054061ffef53b12788916e0dba01","datavalue":{"value":{"entity-type":"item","numeric-id":222618,"id":"Q222618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$17314896-10E7-4B25-86D3-0F515D84E6E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d98a938c7c496671aebe9d069bbd3d70f74a635a","datavalue":{"value":{"entity-type":"item","numeric-id":661944,"id":"Q661944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$3FE32A79-F382-48B5-AA51-CAD83BC952DF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$41591637-1E07-4BB1-9E3E-14E1CBB8F39E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"133f6ae6dfb800b668c32271be33f0f9ba6e88cf","datavalue":{"value":{"time":"+2000-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1306428$6586B1F5-4FE2-43C4-88D8-E3DC8CBDD310","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"acd959f64bca54ae016612ac023a80735f508e42","datavalue":{"value":"https://semanticscholar.org/paper/7017526f7f632c773511187ebd996fa5515a2598","type":"string"},"datatype":"url"},"type":"statement","id":"Q1306428$7D85C71D-0D5A-4286-9E0E-86F4C308E872","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"531c7f4adab2fd60c405c8281a7071f2fe350fa8","datavalue":{"value":"Claw-free Berge graphs are known to be perfect. Chv\u00e1tal and Sbihi proved that a claw-free graph is Berge if and only if every leaf in any clique-cutset decomposition tree of the graph is either ``peculiar'' or ``elementary,'' thus providing a polynomial algorithm for recognizing claw-free perfect graphs; see \\textit{V. Chv\u00e1tal} and \\textit{N. Sbihi} [J. Comb. Theory, Ser. B 44, No. 2, 154-176 (1988; Zbl 0669.05054)]. Their definition of peculiar graphs completely describes their structure. But elementary graphs are defined as those whose edges admit a bicoloring in such a way that every chordless path on three vertices (a \\(P_3\\)) has its two edges colored differently. The main result of this paper is the following structural characterization of elementary graph: ``For a connected graph \\(G\\) the following properties are equivalent: (1) \\(G\\) is elementary. (2) \\(G\\) is claw-free Berge and contains none of the five ``wonders.'' (3) \\(G\\) is an augmentation of the line graph of a bipartite multigraph.''   The wonders are five small graphs called pyramid, lighthouse, mausoleum, garden and colossus. Augmenting a flat edge \\(xy\\) (an edge not lying in any triangle) is a process of attaching a cobipartite graph \\(B\\) (disjoint from \\(G\\)) to \\(G-\\{x,y\\}\\) in a specified way and a general augmentation is repeated augmentation of a set of flat edges forming a matching in \\(G\\).   As a prelude to the main theorem, the authors prove the following characterizations which are of independent interest: (1) A graph is the line graph of a bipartite multigraph if and only if it contains no claw, no 4-wheel and no odd hold. (2) A connected graph is either the line graph of a bipartite multigraph or the complement of a bipartite graph if and only if it contains no claw, no odd hole, no odd antihole, no \\(D\\) and no pyramid.   Here \\(D\\) is a graph on six vertices \\(x\\), \\(0\\), \\(1\\), \\(2\\), \\(3\\), \\(4\\) and edes so that \\(x0234\\) is a chordless path and \\(1\\) is adjacent to all the other vertices except \\(x\\).   Besides a polynomial algorithm implicit in the proof of the main theorem, the authors provide a canonical decomposition algorithm for elementary graphs, and also give an alternative proof of the well-known result that every claw-free Berge graph is perfect.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$FC645217-6A36-4BD4-ACD6-52E05D8DE143","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$E3CE0E7C-2194-4DA7-BBF3-9E15DB84110F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$A9802039-390B-4748-A556-D85E34A224E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$175A7492-7150-4FDC-B2B2-4D4B8F861AF0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4718bedc5f33281b124d2d4a289fff5c20cfb0fd","datavalue":{"value":"1347242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$38DC72FC-C61A-4973-BB7B-C0F54B784AFE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"383f8c40d49a3ae166580a1595836f3292bc52b8","datavalue":{"value":"Berge graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$4C7EAC12-D89A-438C-9E67-C4C837DE9E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef67640bec3c4afe93760825b64ba61c05b28a68","datavalue":{"value":"claw-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$B24D6320-E399-45B0-ADAC-62D36D7BBB79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$210D5FD0-B830-4A4E-BE1D-05E3A8DD00D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$7D986867-B909-4C68-AC84-ADA7B548B8DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d45419e6703fb43f6434b6e7537f46c3da61cd6c","datavalue":{"value":"structural characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$8606A6E6-625B-46F3-93AE-DB72493BE157","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"747ed5530b6e972796d9277d40f3838700756ce9","datavalue":{"value":"elementary graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$EC22870D-634D-4FD9-9109-BA43E64AF091","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$0020FE73-DECD-45B1-8BA8-FEE219AF8158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$11BB44AF-9C9F-48D6-9B9E-FCF4A9F6308A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31f381bdd69582857e56f18e0bc12203f9666202","datavalue":{"value":"wonders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$5006BB24-AD81-40EB-92C5-7FA5CDA26101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"735ef72e5bdf03f4357fa6ec9406b67bfc1a7dfe","datavalue":{"value":"augmentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$A511E6BF-D066-449D-8256-40897236B33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$C950F718-CAF5-4F84-AF2A-9BA173EBD7DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0f5676cd13972c82447aeb9b5b501dd066e7ae8","datavalue":{"value":"bipartite multigraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1306428$568FB072-44A5-4AE0-8A60-F86985CF2FD6","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":"Q1306428$64BDBCBD-58F0-44EA-B6D9-716D8849D1AA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0eb809b40d5f72aadce518bc05536b1b51cc8275","datavalue":{"value":"W2076296189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$895A0D8A-DB6C-4966-AFF0-77AB582685BA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c44b9f5ba4909399c3f5d4300083b5a1a5bffab","datavalue":{"value":{"entity-type":"item","numeric-id":3680833,"id":"Q3680833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$2480A832-FD66-477E-A087-DEF4651788D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54f80bd66875089f385bc846e7e7f8ca82fdf2a5","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$835954E0-790F-447E-8399-969689D50436","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":"Q1306428$EFAD9B65-C80A-4347-914C-371AD320A177","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":"Q1306428$381C88F5-BC33-48C1-B901-FC7A7F355ED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0194643ef28e9a8173abc6bbf30f54f1d43084","datavalue":{"value":{"entity-type":"item","numeric-id":1246434,"id":"Q1246434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$D543251F-5555-4CDB-9C53-E12F70054143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2362ed226b34fd21fa5e856182cb167fecc51e3","datavalue":{"value":{"entity-type":"item","numeric-id":3218158,"id":"Q3218158"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$2DD1AAC2-47F9-4AE8-9756-469673749942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f721405f312fa48c5b5ef170d833c836a8a253","datavalue":{"value":{"entity-type":"item","numeric-id":5554165,"id":"Q5554165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$090F3C3C-0E60-4274-B23E-025A2EA67EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"094c1770040a35473cad41d6fc105bba672f1434","datavalue":{"value":{"entity-type":"item","numeric-id":5184940,"id":"Q5184940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$0C4450E2-C892-44E8-B760-8B60F5EAE56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3c99368ea38ef93edcc839b4081d214aa7efc0","datavalue":{"value":{"entity-type":"item","numeric-id":2553372,"id":"Q2553372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$35F62004-6C7D-442C-A5A7-AAC01ED48CF8","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":"Q1306428$3DA213B3-14E8-422D-8FF7-DA275C8FFCB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c83322ec89a0879c019f012ce18dfec20bc796","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1306428$E1AD3ECB-5226-469D-885E-07AE5E722617","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":"Q1306428$1580866E-E005-41E3-9AB0-68BD137BDA44","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6d5a76bde049335e9215fea8b3470759f65ceefe","datavalue":{"value":"10.1006/JCTB.1998.1872","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1306428$1D181ACE-4DBD-4194-9217-3B4EC56FB680","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91d688146907f1450c658865b3aa86d4f75db662","datavalue":{"value":{"entity-type":"item","numeric-id":5417818,"id":"Q5417818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f54b053681bd2833427aee0b2153dc5a1d876d8","datavalue":{"value":{"amount":"+0.8495825529098511","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":"Q1306428$1C31C788-E36D-4096-A1E2-E87D32B8E164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0455745ef47528cf12c5dccf9da883f6bd5cd93d","datavalue":{"value":{"entity-type":"item","numeric-id":686245,"id":"Q686245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e68c9d9b7a603041f8b03d1933033f54c8bd026f","datavalue":{"value":{"amount":"+0.7940196990966797","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":"Q1306428$803F0FD3-E4D3-47BE-9D8C-9BB5773442EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dacbe37839bd0890cfd12f2957b17067cefc9c1","datavalue":{"value":{"entity-type":"item","numeric-id":947722,"id":"Q947722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae4c958215e65d1414aa982ae903c0e3d5796031","datavalue":{"value":{"amount":"+0.7920272946357727","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":"Q1306428$2C7DD6C0-0CBD-4107-967F-361A0882FD28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37d3c1e987bbb3180327f36a777d076cd318d026","datavalue":{"value":{"entity-type":"item","numeric-id":3416248,"id":"Q3416248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b282d9ebfc519ea8c541ce3b611ba74a2faf9955","datavalue":{"value":{"amount":"+0.788364827632904","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":"Q1306428$69991A1E-C92E-4E8F-B9BD-E2A7607017D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4add5281769213f2043556c93c255714beedfd3","datavalue":{"value":{"entity-type":"item","numeric-id":1112847,"id":"Q1112847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8148e55a9be85c66c8c643a8c58bd008ea1476d5","datavalue":{"value":{"amount":"+0.7876105308532715","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":"Q1306428$AC33F3DD-BBCA-4B53-87B2-E14C57B73814","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A description of claw-free perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_description_of_claw-free_perfect_graphs"}}}}}