{"entities":{"Q1894378":{"pageid":1905120,"ns":120,"title":"Item:Q1894378","lastrevid":71088318,"modified":"2026-04-13T19:24:28Z","type":"item","id":"Q1894378","labels":{"en":{"language":"en","value":"Generalized perfect graphs: Characterizations and inversion"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 777839"}},"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":"Q1894378$E730816C-5A22-44BA-9B32-D933C2A98E36","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"83c4e53b92ece89e0c1199b37354ac09a960f6f8","datavalue":{"value":{"text":"Generalized perfect graphs: Characterizations and inversion","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894378$F26F74FA-B468-45D6-B181-85E0749E5753","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5b6d4cfbf1f9ffe3c82df4e7532bc92be18ba7d5","datavalue":{"value":"0833.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$3B9A002E-A63C-4790-8180-F7F700158AE8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"72237d48bf09cbdc58e5d11f4b2a1ec7f753b826","datavalue":{"value":"10.1016/0166-218X(94)00066-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$496467BF-78A6-4001-BCC6-A44E2FE9E257","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4d32bdb43352779c472e08e65787c883d867f4a6","datavalue":{"value":{"entity-type":"item","numeric-id":251908,"id":"Q251908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$16752112-8942-4B48-B498-844E484A8136","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":"Q1894378$259EE3C2-EEBA-4F5E-A4EE-80F2A0F20D35","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3da5740e8a0078651a07b58d85e873b362b3e452","datavalue":{"value":{"time":"+1996-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894378$A531C5B4-D933-4789-B409-97880453563E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1ebbe3202f5e971506295dd55b987ab14987d279","datavalue":{"value":"The author generalizes the notion of perfect graphs as follows: Let \\(\\mathcal P\\) be a hereditary family of graphs. Then \\(\\chi_{\\mathcal P}(G)\\), the \\({\\mathcal P}\\)-chromatic number of the graph \\(G\\) is the minimum integer such that \\(V(G)\\) has a partition \\(V_1\\cup V_2\\cup\\cdots \\cup V_k\\) with each induced subgraph \\(G[V_i]\\) a member of \\(\\mathcal P\\). The \\(\\max\\{\\chi_{\\mathcal P}(K)\\}\\) over all cliques of \\(G\\) is defined to be the \\({\\mathcal P}\\)-clique number \\(\\omega_{\\mathcal P}(G)\\), and \\(G\\) is said to be \\(\\chi_{\\mathcal P}\\)-perfect if \\(\\chi_{\\mathcal P}(H)= \\omega_{\\mathcal P}(H)\\) for all induced subgraphs \\(H\\) of \\(G\\). The set of all \\(\\chi_{\\mathcal P}\\)- perfect graphs is denoted by \\({\\mathcal P}^*\\).   In the first part of the paper the author `gives' forbidden subgraph characterizations of \\({\\mathcal P}^*\\) for several families \\(\\mathcal P\\), citing her dissertation for most of the proofs, for example, for \\({\\mathcal P}=\\) \\{acyclic graphs\\}, \\({\\mathcal P}^*= \\) \\{chordal graphs\\}. A two-step procedure is indicated to get \\({\\mathcal P}^*\\) for any \\(\\mathcal P\\). The second step involves finding \\(\\{\\text{Free}(K^*_n)\\}\\) for integers \\(n\\geq 2\\), where for a family \\(\\mathcal F\\) of graphs, \\(\\text{Free}({\\mathcal F})\\) is the set of all graphs \\(G\\) which do not have any member of \\(\\mathcal F\\) as an induced subgraph. The author reports only partial success in this.   In the latter part of the paper the author starts from the observation that the mapping \\({\\mathcal P}\\to {\\mathcal P}^*\\) is not one-to-one and tackless the `inversion problem' of finding all hereditary properties \\(\\mathcal P\\) for which \\({\\mathcal P}^*= {\\mathcal Q}\\) a given hereditary family. Several interesting results are proved and many open problems are suggested in the concluding section. Finally, it is amusingly demonstrated that all these ingenious methods leave the SPGC where it is: still a conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$B6AE9F46-D4B3-440C-9979-5BC9FB2A786E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$CF2B0E0C-9F00-4737-AFB7-A842427CE9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$AF7647DA-6E67-4580-8A34-D9796E878044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$96675BB5-652D-4985-A4CA-8CD33FC333E1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"779b54d4d7f7619a1dd56e7cc7b25259250864b6","datavalue":{"value":"777839","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$2443FD09-4127-4562-90E2-6DA82D6447A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$F74CE178-6226-40BB-A20D-CDF8437249CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a153084f07a75cc56b26c617236589c3c4eb947","datavalue":{"value":"cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$5B287630-8719-422C-85CD-AE67CE7D3410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87be2b8675b9f2c4e3ad8db1861493f0c7031e4a","datavalue":{"value":"subgraph characterizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$993463C0-53C8-4C29-83F7-A3F18B43657C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ff660537c46a0ea02613438ef354efbfd3b43bd","datavalue":{"value":"hereditary properties","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$9E436AB7-4849-4CBA-9FAC-560E524C06C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a4d58aa61b8916a5c529cd6719565d8124ba3b2","datavalue":{"value":"SPGC","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894378$2DB7DA75-D54A-4012-AB64-38465E9A22C4","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":"Q1894378$D61BC513-091F-415A-A6D0-C5F9CE4BC28B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d59fb568ab69c8d057b84e4ffc141366f119d24a","datavalue":{"value":{"entity-type":"item","numeric-id":1132889,"id":"Q1132889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$BD048CEC-EE9A-4246-A3B0-EE2E87E74F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$6D88E98B-1B0F-41BB-8CE6-5BDD5441FA54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2def493c6145889772ddbfb9ee64a57941dd9a7","datavalue":{"value":{"entity-type":"item","numeric-id":3748295,"id":"Q3748295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$F01CB5D4-1285-47E8-A7C5-911278865456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed2cf1e3c5cf3c763e86c2665ddd5288c764294b","datavalue":{"value":{"entity-type":"item","numeric-id":2546051,"id":"Q2546051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$A1BD5E0B-57F0-4D22-8B98-C9EA58F10907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$04AA6627-AA73-4473-B69B-576D20204A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$0BD5B0CC-B5CC-4098-AA92-63207EB6DB9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$E6D2D5B8-AE17-4A34-BDB2-D9ECFDC4E7AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f4775e52278958af4d21529dfa1bb7038748fae","datavalue":{"value":{"entity-type":"item","numeric-id":5554152,"id":"Q5554152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$FE5506C4-5897-4541-89B5-C42D33B1849E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07aba3a7c7b9db6e96bc2dd5ba593c5ed156a312","datavalue":{"value":{"entity-type":"item","numeric-id":4056032,"id":"Q4056032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$04021E00-F322-4ECF-9F33-19267816660F","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":"Q1894378$E8073D6B-08E3-416F-AADA-744E9C4D5B97","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":"Q1894378$1420849B-5AC8-4363-9E0D-5ACED45FA44D","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":"Q1894378$6D30C62D-AFF5-4FDC-BE35-C3A773FDBA27","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":"Q1894378$C4356175-EFD9-4F11-ADE3-76BEF4498EE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f2ea9e473a8cf61f64728aa7c6cf40b378a168a","datavalue":{"value":{"entity-type":"item","numeric-id":754232,"id":"Q754232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$29E4474F-9C6C-40F1-863E-9A73907E25F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ee66520b64999e13a39a4a3b7f6b69fc8fdb426","datavalue":{"value":{"entity-type":"item","numeric-id":686267,"id":"Q686267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$1A1F0D05-C04F-4192-9679-F21A33E33F55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"587c9fe6c6d9b277fc4e4fdbf42a96824b3a71a1","datavalue":{"value":{"entity-type":"item","numeric-id":1894378,"id":"Q1894378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894378$ECB7FAB3-6559-4FFC-A147-259BD6DC6648","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":"Q1894378$E7DC05D7-FE1D-455A-943A-A2D17267E1D0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"97bc7d0a1f1c6b75f574266620da835f5cde06c8","datavalue":{"value":"https://doi.org/10.1016/0166-218x(94)00066-m","type":"string"},"datatype":"url"},"type":"statement","id":"Q1894378$C86AEC57-1360-4771-925A-0111E65A2907","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b88400ecd1190f401afb320a8cf588aabd8c8ee5","datavalue":{"value":"W2055939684","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894378$4B788453-9822-4E3B-9550-F871381C8883","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10f0649558f26937e2474fa725696298dfc7ced1","datavalue":{"value":{"entity-type":"item","numeric-id":5284093,"id":"Q5284093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b0bfd9a7b3202c233c52602e5525bdcd2236e6e","datavalue":{"value":{"amount":"+0.8513023853302002","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":"Q1894378$6E8945A7-5FB0-4D7F-ADF7-F20721083257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c20cf256688af4c43a0112ca3119e40fe9fd540","datavalue":{"value":{"entity-type":"item","numeric-id":686267,"id":"Q686267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86cf892662a443b63de999dd30a0b665f7eadb47","datavalue":{"value":{"amount":"+0.8505970239639282","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":"Q1894378$202B7777-7A4F-4FA9-9627-CFC5F068C99F","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":"86cf892662a443b63de999dd30a0b665f7eadb47","datavalue":{"value":{"amount":"+0.8505970239639282","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":"Q1894378$2567A037-E4A1-4AAD-97CC-99F4E61A1887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d8e53686dc801fb6def850de5a8249c2eaf65c4","datavalue":{"value":{"entity-type":"item","numeric-id":1084108,"id":"Q1084108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"748f5fc8dc41464128646088d05a3ba9d238fd10","datavalue":{"value":{"amount":"+0.8167746067047119","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":"Q1894378$16BC89C5-1E1C-4285-8D24-DA92B6FA33F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa303011353dedefdefdd44f491078358d4bf68","datavalue":{"value":{"entity-type":"item","numeric-id":3351379,"id":"Q3351379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a267509160e3dc1c85a8f74714a3283ddf6ab42","datavalue":{"value":{"amount":"+0.8136436939239502","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":"Q1894378$AD2D3B8E-111F-4656-BE63-53426E7DBBE3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generalized perfect graphs: Characterizations and inversion","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generalized_perfect_graphs:_Characterizations_and_inversion"}}}}}