{"entities":{"Q686267":{"pageid":688116,"ns":120,"title":"Item:Q686267","lastrevid":63608787,"modified":"2026-04-11T14:19:40Z","type":"item","id":"Q686267","labels":{"en":{"language":"en","value":"On generalized perfect graphs: Bounded degree and bounded edge perfection"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 428115"}},"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":"Q686267$AA86FA70-BF2E-4806-885F-3260ED2D2C54","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"84881c77de23681bbbc90ac29f84fc1768f22b8a","datavalue":{"value":{"text":"On generalized perfect graphs: Bounded degree and bounded edge perfection","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686267$7A14EFFB-F897-4E7A-9782-94A3F97C73CB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6737f79fe855b7191d2a9315f28a41e4864519a5","datavalue":{"value":"0790.05028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686267$373941AF-11D3-45E9-9CB4-1C33EE43D3F2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b8755548311a19fd55b862400af9e1d3763a3775","datavalue":{"value":"10.1016/0166-218X(93)90234-F","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686267$DD5D00DF-ADF4-4AAB-AF83-D55E6F01FF5B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e437888af5062d34307fbd29774fb099de05430a","datavalue":{"value":{"entity-type":"item","numeric-id":540119,"id":"Q540119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$8CF0C4B9-3840-4B3D-B98B-B8F0817FF7D3","rank":"normal"},{"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":"Q686267$D6292B17-84CA-46AB-9375-2BD412BA4447","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":"Q686267$4D834B93-951F-4D4F-B454-2D58E2E8A2D8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b6cd5815201d85bb68894181f8a778e0395c5390","datavalue":{"value":{"time":"+1994-06-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":"Q686267$D18C8601-A474-4ACF-88E8-3B57199811F8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1bd912faf8bb66d2fc9cb78a954da0c88285461b","datavalue":{"value":"Let \\({\\mathcal P}\\) be a hereditary family of graphs. The \\({\\mathcal P}\\)-chromatic number of \\(G\\), \\(\\chi_{\\mathcal P}\\), is the minimum size of a vertex partition such that each part induces a subgraph in \\({\\mathcal P}\\). If \\({\\mathcal P}\\) is the family of edgeless graphs, then \\(\\chi_{\\mathcal P}\\) is the usual chromatic number. Define \\(\\omega_{\\mathcal P}(G)\\) to be \\(\\chi_{\\mathcal P}(K)\\) where \\(K\\) is the largest clique in \\(G\\). Define \\(G\\) to be \\(\\chi_{\\mathcal P}\\)-perfect if \\(\\chi_{\\mathcal P}(H)=\\omega_{\\mathcal P}(H)\\) for all induced subgraphs \\(H\\) of \\(G\\).   The authors examine analogs of the Perfect Graph Conjecture (PGC) and the Strong Perfect Graph Conjecture (SPGC) for various heriditary families \\({\\mathcal P}\\). The PGC says that a graph is \\(\\chi_{\\mathcal P}\\)-perfect if and only if its complement is \\(\\chi_{\\mathcal P}\\)-perfect. The SPGC says that \\(G\\) is \\(\\chi_{\\mathcal P}\\)-perfect if and only if neither \\(G\\) nor its complement contains an induced odd cycle of length five or greater. The PGC is true for the usual chromatic number, but there are heriditary families for which it is false.   The authors prove the PGC and the SPGC for the properties ``has at most \\(t\\) edges'', and ``has maximum degree at most \\(t\\)'' for \\(t>0\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q686267$A6D47787-B5B7-40AC-B8A6-A232E96D085B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b687a818ec58a93e77f94a71ec71ff4e2750b160","datavalue":{"value":{"entity-type":"item","numeric-id":592090,"id":"Q592090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$B9EA1C01-D617-4F70-BC1E-7C9696F66969","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686267$9CEE9678-1BCC-4752-84FB-CDCFFED7AF3E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aee284c3fbf4821c15a4f7ffb4da21edac7a50a1","datavalue":{"value":"428115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686267$A5C7569E-D0E9-48A1-9CAF-E7835E7C8187","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q686267$693FC536-4CE3-4AC2-8053-B31A843495CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c31f5f4a8036cc064c09e3ddb9c0fb9fea13e4","datavalue":{"value":"perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q686267$88423F77-A78D-4FAD-A236-2BA6BAD7E530","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q686267$72619649-E972-4885-9C76-2050C65C6273","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":"Q686267$0473BB0C-4B1D-4A32-9753-BBFF5A144417","rank":"normal"}],"P223":[{"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":"Q686267$AA5AAD79-8895-4549-80C0-E76EC00A2483","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":"Q686267$33D706FB-A54B-4F01-BE7A-DAC01CABD89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"513be662bccdbd546ef251f851750f24d2e2aa41","datavalue":{"value":{"entity-type":"item","numeric-id":3474679,"id":"Q3474679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$7880196F-6998-4397-B7FB-5263CF3594CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8233d277b3ded6133706ab325d38fe3bb56ae553","datavalue":{"value":{"entity-type":"item","numeric-id":2529589,"id":"Q2529589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$B65292FA-F664-4567-889C-599C6692D280","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":"Q686267$1B166321-1D37-46AE-97E4-74FCB8BB40D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0246aa2c7e876b33140a3452c2194007249981c5","datavalue":{"value":{"entity-type":"item","numeric-id":4733881,"id":"Q4733881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$01569316-32FB-4D1E-B245-732FB239D415","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":"Q686267$50318FCB-53CD-4EED-9B15-0B4466153FB4","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":"Q686267$0758AF9A-4006-47E2-B58A-782403E8B1AF","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":"Q686267$CDA0A6CF-8989-4137-9A22-37BE1DC8B51D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b64ab0ef8c41ad37822937f4c0720f29374f1c6","datavalue":{"value":{"entity-type":"item","numeric-id":5284093,"id":"Q5284093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686267$F6AEF7A4-878F-4BE3-81EA-FD516CBE11E9","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":"Q686267$53F6188E-8DD7-4FC3-A886-E8374E034270","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"265493401e541234b600f2c94b09017d39ea03dd","datavalue":{"value":{"entity-type":"item","numeric-id":1910576,"id":"Q1910576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56cc09a7e38c1d5e044520de04cc81b3d6e303a4","datavalue":{"value":{"amount":"+0.9134498","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":"Q686267$B3547670-C738-434A-9953-2216A02CAF39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47d6dae7d2810cb232d650580df3a35215528ccc","datavalue":{"value":{"entity-type":"item","numeric-id":4892347,"id":"Q4892347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d663fd1026af228bdbc39c72658eca181dc1bd3","datavalue":{"value":{"amount":"+0.90202636","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":"Q686267$8342A865-69B1-48E3-8742-87E96B5C1561","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6160acbf13cee357c475f0491c5b04348a2ab949","datavalue":{"value":{"entity-type":"item","numeric-id":952634,"id":"Q952634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efda9a1e20d0c79b20cff6f58c67f7ee7fb3cfff","datavalue":{"value":{"amount":"+0.90088755","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":"Q686267$D67C6C87-9E72-4D2C-8840-5C023B924F02","rank":"normal"},{"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":"bae1006c4b96d2f18afa180cd10f43322c95b5c0","datavalue":{"value":{"amount":"+0.8990499","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":"Q686267$58754737-D9AF-48F3-A31A-6F0377FAFE1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63379e1720e3df6603e8145fd963d000db4920f7","datavalue":{"value":{"entity-type":"item","numeric-id":3680854,"id":"Q3680854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ded57a2aa45d0f80246a59800e9308967fda9596","datavalue":{"value":{"amount":"+0.8965767","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":"Q686267$B74C85CF-6E94-47C9-8A07-F4BDDC43856D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f415d74bd1aec3c46e681a19aabeae0494e7abf2","datavalue":{"value":{"entity-type":"item","numeric-id":2444147,"id":"Q2444147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c7ee69e599d92cb433ba1868d83420bdd9cb4b8","datavalue":{"value":{"amount":"+0.8948028","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":"Q686267$89973D88-9E17-4E42-9716-E8BF8AF2910E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7072c34caffd1251f969a09fcf954760858e8d21","datavalue":{"value":{"entity-type":"item","numeric-id":6132532,"id":"Q6132532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"97b19c37e1742e803cec3835439a8e15f2974bb5","datavalue":{"value":{"amount":"+0.8944203","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":"Q686267$1EACFA61-C38A-4931-AB85-47C5D6D4101E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce904569b2f60ab00ce52d9eb9869797b8e5094e","datavalue":{"value":{"entity-type":"item","numeric-id":4522468,"id":"Q4522468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8cc08373cf84387b930e0b7af30a570f6c467aab","datavalue":{"value":{"amount":"+0.89291024","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":"Q686267$0916C496-5103-4B8F-B4DD-A6C701408131","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa06385a608fccd8488d4fdbcf0c23d33d05e497","datavalue":{"value":{"entity-type":"item","numeric-id":4300578,"id":"Q4300578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"770e07c8b6a80b2194b08115ba2c2a592da56799","datavalue":{"value":{"amount":"+0.89285696","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":"Q686267$8BA5349A-CD78-4231-96AF-4DE26A7F3365","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"221907549f5dc7f56b8732ee47f34e43ceddb339","datavalue":{"value":{"entity-type":"item","numeric-id":4719328,"id":"Q4719328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d138d52e570f35fc6082b0d60075fb78c7a2dbdc","datavalue":{"value":{"amount":"+0.8921678","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":"Q686267$24D17C79-034A-4FBC-9325-D550F64C6C08","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On generalized perfect graphs: Bounded degree and bounded edge perfection","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_generalized_perfect_graphs:_Bounded_degree_and_bounded_edge_perfection"}}}}}