{"entities":{"Q1334944":{"pageid":1345683,"ns":120,"title":"Item:Q1334944","lastrevid":68494392,"modified":"2026-04-13T00:05:16Z","type":"item","id":"Q1334944","labels":{"en":{"language":"en","value":"Perfect graphs with no \\(P_ 5\\) and no \\(K_ 5\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 644735"}},"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":"Q1334944$F7379231-8707-4ED7-AECD-2A437AAF19AC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"02aa897c6c7e76a65bbce8f597ebda7a5503a76c","datavalue":{"value":{"text":"Perfect graphs with no \\(P_ 5\\) and no \\(K_ 5\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1334944$3866CD83-F628-4C7F-AEB7-844E74A18DBC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"650796e5f21dcf3001363d139e890ba0445cfc47","datavalue":{"value":"0806.05052","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$0CA1011B-C477-4E15-8CE9-6197A968417F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f88f7c8c469fda7e7eccee58c06c752c29e150e4","datavalue":{"value":"10.1007/BF02986662","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$A7E9FECC-B672-41B2-B95D-40B277FB4E14","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":"Q1334944$0937EDCE-AC94-4E8E-A2C4-1D04155C2AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6eccd330e58db916925e9726f6d3cc506f17a2da","datavalue":{"value":{"entity-type":"item","numeric-id":442401,"id":"Q442401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$E8C5EF5B-2B31-46F3-99D8-477403192655","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$51936A74-2C9B-4961-AA3E-24EA98985A7F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a07e8af38f76d1e005ebe63136b3f3c24a5ff2b8","datavalue":{"value":{"time":"+1994-09-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1334944$7313E6E5-63EF-4FED-9192-A908C07DD3D0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d74f1c8837040a9efaa81ea2060238d6ce59e7e3","datavalue":{"value":"A graph is perfect if its chromatic number is equal to the size of its largest clique. C. Berge's strong perfect graph conjecture [\\textit{C. Berge}, Les probl\u00e8mes de coloration en th\u00e9orie des graphes, Publ. Inst. Stat. Univ. Paris, 9, 123-160 (1960)] is that a graph is perfect if and only if it does not contain an induced subgraph isomorphic to a chordless cycle with at least 5 vertices or to the complement of such a cycle. This conjecture has been shown to be true for graphs not containing certain forbidden induced subgraphs, for example a 4-clique [\\textit{A. Tucker}, The validity of the perfect graph conjecture for \\(K_ 4\\)-free graphs, Perfect graphs, Ann. Discrete Math. 21, 149-157 (1984; Zbl 0566.05028)]. In the paper under review, it is shown to be true for graphs with no induced length-5 path and no 5-clique, from which it follows that a graph with no induced 5-path, 5-clique, 5-cycle, complement of a 7-cycle or complement of a 9-cycle is perfect. This class of graphs is shown not to be contained in any other known class of perfect graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$7C8519C6-2802-457B-99E3-3953E1917D1C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$91825BC8-359D-41D8-84FD-9FA02E3AA18E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$BCCE7F2D-1041-4203-A94E-DCF07F0B23CB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4a99d8ed1e98e94f49f2811ca76f6a7eeae9cf9","datavalue":{"value":"644735","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$ABDEB466-D3C1-40D0-B426-1399C93EA713","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$A134242A-F10C-43E9-9EC1-C7277DA46255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5928c9dcfb061445431e40c46be3050e6d5dbf83","datavalue":{"value":"clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$0DA389BB-1E92-4744-A087-1742A629ADA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$B7509D7B-6C4F-42D9-A1F8-605781236CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f8854b5e4a0017c2e603242cf5eca1a042ef5e8","datavalue":{"value":"forbidden induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$83F23465-C0DF-4AAC-9224-965B4E938F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a6072fa2abea179a7709e57b96ad2802601bb845","datavalue":{"value":"perfect graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$2354811A-FB12-4898-A5AE-64F359673953","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f6e8f29f2404bb06ed6c5be70e3d10cf68a7e7a","datavalue":{"value":"5-clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$B762054E-5D42-434E-B0C6-1FEFF070F8CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c32168fc6a2f9203fdffc00dda33ad049d91da69","datavalue":{"value":"5-path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$A627E66C-3FB4-4E27-8C35-C6838CD1DF06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75d634add9ed0002d82a2e16457c7cdb21a990cf","datavalue":{"value":"5-cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1334944$038D857F-CD0A-4769-82EC-B44B5BCDA5AC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$2B45A8E9-B469-4D30-B4F1-71020F1F8F62","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":"Q1334944$0ED7FBBC-5E66-46F8-80E8-14F9201A9ABA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22ad8c0cf8959fb3be24778fa28798afcfd7af02","datavalue":{"value":{"entity-type":"item","numeric-id":3286847,"id":"Q3286847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$F86CB274-1256-4335-AA97-53C47F3C66F8","rank":"normal"},{"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":"Q1334944$867145FD-7B9C-4C31-89C1-3FC33DB0C91E","rank":"normal"},{"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":"Q1334944$DA1C06E8-2CB5-4534-B214-A65556687138","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":"Q1334944$E1A40752-F48E-4322-BC6C-889C894B7B63","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":"Q1334944$841F0B9E-8AFA-458D-82BC-B2FCE7F39163","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":"Q1334944$1E26BE0C-B932-43D0-9471-D55710695C11","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":"Q1334944$B897E051-2517-4963-9226-EE504EE0B699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41edeebde06937350247d6fc2614b510a7e56a8d","datavalue":{"value":{"entity-type":"item","numeric-id":804585,"id":"Q804585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$A706085E-1F22-481A-A673-4D0F75A0C735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f14929504188a53ef660023bd30753f8781f60c","datavalue":{"value":{"entity-type":"item","numeric-id":1104342,"id":"Q1104342"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$56D1E306-0BE5-443C-B9F6-D1C5BECD98FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39b851e406aa7071875e5e8a730aed77089dbc45","datavalue":{"value":{"entity-type":"item","numeric-id":1108293,"id":"Q1108293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$73CE8CFF-F80E-4B7B-A733-B0D6CD54D750","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":"Q1334944$8FFCC9E7-7D76-47C4-8179-2425A45FA4CB","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":"Q1334944$2389B555-DEAC-4BBB-BBE4-0AEF32DAD864","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82b35ab1dd3afe9b3d87abd5cfd205aad108c206","datavalue":{"value":{"entity-type":"item","numeric-id":1105623,"id":"Q1105623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$0C179000-9D33-4A61-A8AD-C748A1C51445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4754f01c6e5f4fbaf7f8521f5e41346da3c07f","datavalue":{"value":{"entity-type":"item","numeric-id":2563166,"id":"Q2563166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$3845D0BF-E629-4F3B-B580-536259F881DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0fc55fcfa10f65c87858c7cb77889a9a30936449","datavalue":{"value":{"entity-type":"item","numeric-id":3680855,"id":"Q3680855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$BCBE0105-13FD-4785-996E-81D6CAD0E8F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d12752e7e3b87a1df82f1629f2c888413b32ca16","datavalue":{"value":{"entity-type":"item","numeric-id":1071025,"id":"Q1071025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1334944$1FA9E7D2-84C3-416D-BC22-17BCDCFCEF20","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f09fc3d359b3f397453b33b84fa8d4ecf9ada265","datavalue":{"value":"https://doi.org/10.1007/bf02986662","type":"string"},"datatype":"url"},"type":"statement","id":"Q1334944$53089358-1D42-4931-9C1A-438BCFC837E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c6a33da0425937134235eccf5da39a067eec50ad","datavalue":{"value":"W2483513242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1334944$3E59FF90-9F95-413D-9154-AB6CD8BBF95B","rank":"normal"}],"P1643":[{"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":"e3b3b0a8f67cb8d58366e596aebccbf5817b2bcd","datavalue":{"value":{"amount":"+0.9108915328979492","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":"Q1334944$E30881B5-2CDD-42D7-BECD-9CB605D80043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"250399cdd7c6dd55a719533a32ed45d52eaad36e","datavalue":{"value":{"entity-type":"item","numeric-id":3476848,"id":"Q3476848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f204adc9cf6615c1a209cb61b954c36c46f5362","datavalue":{"value":{"amount":"+0.8935322165489197","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":"Q1334944$3E0AFDE1-5D2C-4A5C-8453-3E8A83A0D171","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b41cdd6c68a4b0175bbdb432c97bbe800cc41448","datavalue":{"value":{"entity-type":"item","numeric-id":1293187,"id":"Q1293187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84a30fc8c0c1abb464f55369ead1f01458a68678","datavalue":{"value":{"amount":"+0.8881826996803284","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":"Q1334944$8FCDA677-7F4E-4366-87D1-86B81A7C6B81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"294b86cacba0294014f6420efa4898597892e71c","datavalue":{"value":{"entity-type":"item","numeric-id":1112848,"id":"Q1112848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8b6e887b4b405357b8c09ab3b18a79b7bc410ca4","datavalue":{"value":{"amount":"+0.8813772797584534","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":"Q1334944$A8F7CCA1-FFD9-4B81-8FED-D5B27F21E14C","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":"d2ca96220fb637f1f3abb16f48fa0f6c4dbb9d16","datavalue":{"value":{"amount":"+0.8687816262245178","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":"Q1334944$8338119C-1236-43C8-992C-603467D85BBE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Perfect graphs with no \\(P 5\\) and no \\(K 5\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Perfect_graphs_with_no_%5C(P_5%5C)_and_no_%5C(K_5%5C)"}}}}}