{"entities":{"Q1613431":{"pageid":1624171,"ns":120,"title":"Item:Q1613431","lastrevid":47977075,"modified":"2026-01-03T06:06:30Z","type":"item","id":"Q1613431","labels":{"en":{"language":"en","value":"On (\\(P_{5}\\), diamond)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792368"}},"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":"Q1613431$1BCB8494-7A88-4287-B9DC-C4F16178DF7C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2dbd2303747f0bdaa313ed0902d89f3dc801d25f","datavalue":{"value":{"text":"On (\\(P_{5}\\), diamond)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613431$D94F17A3-5936-4AC3-883A-088707E4A5BA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a2287bab918a0da08ee023a254b90359cafe8268","datavalue":{"value":"1004.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$E2DA7EE8-E876-4FB3-A270-D49B68B692E3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"772b5b4e84e7ef065e39356cba5a619041ffb61f","datavalue":{"value":"10.1016/S0012-365X(01)00268-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$FC379F3F-2E2F-4504-BD89-081AF5CD6360","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"268c86183b2f5c73b7d063861a79c1303bb9cf99","datavalue":{"value":{"entity-type":"item","numeric-id":429691,"id":"Q429691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613431$199B1014-4889-4936-ABC7-30E2F3558B75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d1cf9debe45e382f5f77b3553301ae0391bc889d","datavalue":{"value":{"entity-type":"item","numeric-id":222633,"id":"Q222633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613431$317E93AF-6D1A-4ED8-A226-E876B8C2D6B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613431$B8051265-AF6D-4FE5-B565-33CA79B58268","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613431$9D48D619-035A-4B20-A08A-BE6271AED0AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7515e8f9a97c5f68a58f15364520e25f41706886","datavalue":{"value":"The authors study the stable set problem (SSP), the coloring problem (CP) and the clique cover problem (CCP) of graphs with no induced path on 5 vertices \\((P_5)\\) and no induced diamond \\((K_4-e)\\). They give polynomial algorithms for solving CP and CCP on such graphs. As for SSP they improve previus \\(O(n^4)\\) time bound to \\(O(n^2)\\) for these graphs. They also show the possibility of desribing imperfect (\\(P_5\\), diamond)-free graphs via elementary graph operations such as vertex multiplication or substitution from a limited set of small basic graphs. Corollaries of this result and other structural properties are a complete description of the stable set polytope for imperfect (\\(P_5\\), diamond)-free graphs and the existence of a non-trivial subclass of these graphs whose elements are \\(h\\)-perfect but generally not \\(t\\)-perfect.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613431$BF0F2404-A8E2-4F9A-8EF0-C19477662819","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":"Q1613431$58AC11C9-5ECC-43D9-B4C9-1629ECE59C17","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$4EAD4794-ED00-4AC6-973B-5C68EB544858","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e409eb44902873893a0f6988ee9577058bcb2578","datavalue":{"value":"05C17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$A74E49C8-3FA4-46CC-B0E9-C92765C3EFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$23F04A48-A975-4B90-BEDE-705BCDD84746","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"496051188df7573b61e4068db8990359d61c67ad","datavalue":{"value":"1792368","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613431$3B1D55CB-FFA5-4D4A-81D1-1E6A3CCB242E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b5b3a09094024e62bc4a7e47d469b459760b5cfd","datavalue":{"value":"stable set problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613431$47212051-EBDF-48E3-8250-28795F1E1572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"112e98fa36a3027fc4180f9b14b725872529c1ba","datavalue":{"value":"coloring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613431$0864854B-E521-4D74-B5D7-DD6C6D4998EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2e099cc3a350d39c2e62d0aaa45072bdf52138","datavalue":{"value":"clique cover problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613431$2354703F-B9BA-45A2-BC6F-458D3D67F839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613431$9BCAE8C2-6C94-4265-BE6E-A2F0C5C8E0C2","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":"Q1613431$1FE76169-BF02-455F-A3B5-A8AF8B366883","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e83f4c339b37cbd72ba06b2401024de302cb7888","datavalue":{"value":{"entity-type":"item","numeric-id":5900786,"id":"Q5900786"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c893994434fc678acc8a2f6908d05d964f25220f","datavalue":{"value":{"amount":"+0.8429880142211914","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":"Q1613431$65C48713-165A-4E48-81AB-04A521132BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"641d99fde587bf4f2d6666a5abd6674cb037295a","datavalue":{"value":{"entity-type":"item","numeric-id":1861559,"id":"Q1861559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f672e7ba77a9ea2a3941cb413664a337479bc7cb","datavalue":{"value":{"amount":"+0.837303876876831","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":"Q1613431$805F5D51-AAAB-4B2C-9281-C8A804594C87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ee0c966f461949c8f8e20a273670430a147108c","datavalue":{"value":{"entity-type":"item","numeric-id":817767,"id":"Q817767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fdb9a544d49a4d832816cba0eacaf7fa82c07da","datavalue":{"value":{"amount":"+0.8335797190666199","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":"Q1613431$F1B3A0B2-D9D8-4A8D-AB46-59B93D2AFC1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58b1a2593f003457a3abcfd04fba636d98cd200f","datavalue":{"value":{"entity-type":"item","numeric-id":1428548,"id":"Q1428548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19894d178eb90fff9ffbff1e96524d1ca7ed0ff9","datavalue":{"value":{"amount":"+0.8326742053031921","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":"Q1613431$B634B964-046A-4ED0-8E2D-3352909A3E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c057ae6b12887c2aef5d0a2f3e62eb8dff627d98","datavalue":{"value":{"entity-type":"item","numeric-id":4915195,"id":"Q4915195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68ec1e617ff44e3290b226e69140c08ee667d90d","datavalue":{"value":{"amount":"+0.8237716555595398","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":"Q1613431$EA9857E1-D325-42A6-9FBB-DF28A569FBAE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1613431","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1613431"}}}}}