{"entities":{"Q1895822":{"pageid":1906564,"ns":120,"title":"Item:Q1895822","lastrevid":69072825,"modified":"2026-04-13T04:27:04Z","type":"item","id":"Q1895822","labels":{"en":{"language":"en","value":"Recognizing bull-free perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 784145"}},"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":"Q1895822$BE474153-CC42-434B-9CD7-2FEE0396E639","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fc570c64f21b4349ec909b439a29250484f08dcc","datavalue":{"value":{"text":"Recognizing bull-free perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1895822$CF09E652-1FD4-4823-A9C8-ACA0BB0E343D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0058a2f7d10577795666065c52d83ef52513b8f8","datavalue":{"value":"0832.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$6BAC64AF-CDA6-40E9-A7B0-2C506A9B888A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4d459d07f7c538ea360050e8eaa125ff88082f8","datavalue":{"value":"10.1007/BF01929485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$692F0D6A-54D7-402B-92DE-8031A9D9AD82","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b2077c4d9eb84e4e88b8f12232421e4e16db79a9","datavalue":{"value":{"entity-type":"item","numeric-id":1095937,"id":"Q1095937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895822$0E51DDA3-C739-4EBB-A8CB-F68AA8BA2E66","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":"Q1895822$0190117C-0633-4AC7-9EBC-FEA3E1604CF6","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":"Q1895822$837B49BE-9390-4F7E-9A12-43C84FA38C5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5eaeb2c9097fea69c487fbd2ea3e5d8c5e6a6b7a","datavalue":{"value":{"time":"+1996-02-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1895822$2D538C5C-FF12-4B35-8A31-28A45728A1D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d02477f30d086e05f38af10b1efce39e2ed9479c","datavalue":{"value":"A bull is the graph obtained from a triangle by adding two pendant vertices adjacent to distinct vertices of the triangle. A graph is perfect if for any induced subgraph \\(G'\\) of \\(G\\) the clique and chromatic number of \\(G'\\) are equal. In 1987, Chv\u00e1tal and Sbihi showed that the strong perfect graph conjecture holds for bull-free graphs. In this paper the authors give an \\(O(n^5)\\)-time recognition algorithm for bull-free perfect graphs, where \\(n\\) is the order of \\(G\\). Note that the general perfect graph recognition problem is in class co-NP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$C5F404CB-985D-49B8-8829-030D4E044B24","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$E351F5FC-F3A2-406C-8139-594EE4FDCC90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$8B33BA09-DCE8-4340-813F-8D0F68AA5013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$BABC607A-82EB-4669-9BA4-657EFF2383D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$643164D2-4126-4A4E-9508-7D607C33D88A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a75d8f3f601b51aa786b2819a22099cacaa8252a","datavalue":{"value":"784145","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$7F8B19D6-C923-4556-BB4E-111B77D3EE35","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bbabd615306bd49f8fab2a684552f54455258f63","datavalue":{"value":"bull","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$549A3547-ADBD-4918-A811-EEED3CC8E31D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$F5075D58-ED08-4AE8-91E0-2DA030B8641B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a11116a6b4821127d46d686f666f969b50e0a4e","datavalue":{"value":"strong perfect graph conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$7FD77192-E001-4E15-9509-B8C14F0A6682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$47D43F59-2D1B-4E06-8DB4-93EF11E4425F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d726a45cd232f9d6032fc66bca9225d763794f35","datavalue":{"value":"bull-free perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1895822$EEB5D5CF-C60B-4920-8761-C90511174390","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"24a28ef6d6604354942779939ac03d56e4d184d2","datavalue":{"value":"Q64012590","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1895822$28717044-4E89-4388-A309-FCD0DF8CDDF2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db03c62d3fdb76a66177e81b54d14a2f5ae490f1","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895822$4D8B35BB-CD60-4BD0-8C9B-E91502397AD6","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":"Q1895822$5862B4A8-7013-4D89-A040-9A65B7A785F7","rank":"normal"}],"P223":[{"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":"Q1895822$E85FE2BC-18A7-48BE-8D72-0B9C519FEF67","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":"Q1895822$7636BB60-E797-411E-B47C-0CB212584E2F","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":"Q1895822$7A6AFBE2-2288-4740-9737-ED776DFA1C82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895822$69550B81-3DA1-4431-8FE2-EA387375FB7F","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":"Q1895822$047EDC77-865E-4EE6-AF41-8A2499DE8D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895822$0E86B2DD-135E-4FA2-92A8-CAECB9125B4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1895822$D3DD24E4-EF18-404B-B4C1-E3B69D6AC6F3","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":"Q1895822$57F76FB4-C324-4A58-A841-A12ADC2FFCC0","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":"Q1895822$FCB53CDC-9C8C-40DC-A44D-EB9FF4E77F73","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"264681d13bdde4502bdd73db33f2e9b8137dbfc0","datavalue":{"value":{"entity-type":"item","numeric-id":2852609,"id":"Q2852609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"38d47c7530a848eca0f4e4306dacbdce7f1f9946","datavalue":{"value":{"amount":"+0.9359018","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":"Q1895822$A92AA4F7-98D5-41BD-BA9A-FE574D4AAEA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e4342b0374a195c9ff75e403d7ebbe8769f4a99","datavalue":{"value":{"entity-type":"item","numeric-id":675887,"id":"Q675887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6331c1a88fe8886b98d40a3302d96e85a03da265","datavalue":{"value":{"amount":"+0.93499947","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":"Q1895822$8CF8FEC7-7FEE-4A11-9A72-6B8EFB6A2166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67fac89379722e00cb9389b68c38d55d7a9a6ee5","datavalue":{"value":{"entity-type":"item","numeric-id":4680732,"id":"Q4680732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93f3dba2341a6a934dd4b73a6d86486ca493493e","datavalue":{"value":{"amount":"+0.9094074","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":"Q1895822$D26DABD3-2554-4ED2-9FBF-3B50C28B0A41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d3a2585cce289f0e08f8d0fc283c0ed27e1ad2a","datavalue":{"value":{"entity-type":"item","numeric-id":1095938,"id":"Q1095938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e755a7803e39dd436c270a25b91a81cb0037053b","datavalue":{"value":{"amount":"+0.9043864","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":"Q1895822$CEB76655-EEA3-4FC0-9EE8-3A4CC0C7C1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d424f3de8e17a9e8752f9cbadebb783c1aafca3a","datavalue":{"value":{"entity-type":"item","numeric-id":4899063,"id":"Q4899063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f01417318cad9d4b02a1bd8f4ecde3d1aa3f5b4a","datavalue":{"value":{"amount":"+0.9018297","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":"Q1895822$C89CF4C1-4F75-473B-8230-D167ADE85C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcd65e00fee718257901f2187b17f478985de759","datavalue":{"value":{"entity-type":"item","numeric-id":4652633,"id":"Q4652633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bb58f11948c580e3820d35ea6b2a8d2295c875c","datavalue":{"value":{"amount":"+0.90111697","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":"Q1895822$B33817F9-815C-4315-86FB-1D06CD23F932","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f5be330b21b29ed0815bc6420626d9238c2cb7b","datavalue":{"value":{"entity-type":"item","numeric-id":1118619,"id":"Q1118619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4f0e4e740eb7d214ed9d6575307c3ddce110682","datavalue":{"value":{"amount":"+0.90032136","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":"Q1895822$2435661A-4EBC-4225-A664-CA17ED6836CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce4eba77351276f79b7d6319b7d37db955e0cbc6","datavalue":{"value":{"entity-type":"item","numeric-id":4952598,"id":"Q4952598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66335e5d70981f0afe27b7c1db94109452bfa059","datavalue":{"value":{"amount":"+0.89747334","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":"Q1895822$722AEF7D-C681-4C38-970D-B4C8EC307247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706646c5ec7624ff64c7e5e38d9fa854ab6fb321","datavalue":{"value":{"entity-type":"item","numeric-id":3149869,"id":"Q3149869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2649d9bb39cb5dccdf1ee895759f510859da7ea","datavalue":{"value":{"amount":"+0.8974731","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":"Q1895822$8BF6A84E-1AEC-400A-BDDA-2DF130B7675C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4abacf177ee761ab7f57412390705ee97ec6db64","datavalue":{"value":{"entity-type":"item","numeric-id":4871157,"id":"Q4871157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a18dc024cece18c04e5ad630c674d969554074e","datavalue":{"value":{"amount":"+0.8867357","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":"Q1895822$67B2D14C-584D-42CA-BF2B-B512CCC244CB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Recognizing bull-free perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Recognizing_bull-free_perfect_graphs"}}}}}