{"entities":{"Q2640608":{"pageid":2651351,"ns":120,"title":"Item:Q2640608","lastrevid":49464157,"modified":"2026-01-07T05:09:30Z","type":"item","id":"Q2640608","labels":{"en":{"language":"en","value":"Two-colourings that decompose perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4187831"}},"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":"Q2640608$B843FDD1-7EBC-42D2-8FD8-3A103D9C7770","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2279154eed09e0672b44cf82f8bc57b130eb39f6","datavalue":{"value":{"text":"Two-colourings that decompose perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2640608$C9654D4C-5873-4F1F-810E-6A9BD517F29F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"37596c5eb9806c46147e977ae239334ccc2a5795","datavalue":{"value":"0721.05019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640608$AF7F9E48-B1ED-4776-B9F5-5003D4659818","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"77bc94dd06aa4ef49d04bb18e36daa0a2df15588","datavalue":{"value":"10.1016/0095-8956(90)90061-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640608$E5E2D635-3611-4C58-925B-842D9E519206","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"42c33d3d516bcf7a7a7968560a1817b77f2fffdd","datavalue":{"value":{"entity-type":"item","numeric-id":641184,"id":"Q641184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$65AC882C-6220-42E3-B3C7-6EC13A293590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70470388811b430ae63918166a25d5e4f1096bd1","datavalue":{"value":{"entity-type":"item","numeric-id":501675,"id":"Q501675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$2A6349D5-9529-4DC6-933A-949E34E94A76","rank":"normal"},{"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":"Q2640608$E60823DC-7D3E-4634-8629-C94168440EAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$5AD5FB52-6281-4A21-A659-AA698831F005","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2640608$A68F6860-F949-4E10-9361-A5E525FCE9D1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8ebd779b9835bbd54b0942a2e42ea5c213e0d1df","datavalue":{"value":"A theorem of the first author and Ho\u00e0ng [the first author, J. Comb. Theory, Ser. B 39, 189-199 (1985; Zbl 0674.05058)] states that if the vertices of a graph G are coloured red and white in such a way that every induced path \\(P_ 4\\) with four vertices has an even number of red vertices, then G is perfect if and only if each of the two subgraphs induced by all the vertices of the same colour is perfect. Such decomposition results are interesting, for example in connection with the question if perfectness is an NP problemtype. The present paper provides a complete answer to the question: ``What sets of constraints (on the ways in which each \\(P_ 4\\) can be coloured) have the above property?'' Five new theorems of the above type are obtained.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640608$102F7056-F896-4FA8-B832-AB171A3C4C92","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640608$C2BCBC26-CD0B-4F81-811C-F5FF4AD1286B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b5108403fab755941366291384121b99176d742","datavalue":{"value":"4187831","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640608$768EF240-5CB3-4050-86F3-006876417606","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640608$96705AF3-EC36-4F8F-BF73-C9131204F0A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cee46e2c6a42a74803d50f6329947494bb4a53f6","datavalue":{"value":"graph decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640608$0761E17C-242A-42F9-92F3-F215188D1323","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e44c57c80ad543e3c9f62e0b16b5b17998cd343b","datavalue":{"value":{"entity-type":"item","numeric-id":286762,"id":"Q286762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$EDBD96C0-37E3-40DE-B035-CFCF1DE02397","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":"Q2640608$C088A55A-2A18-4B5A-A0B6-4A5C9311178D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7df59bb137305dcc8c143a7ee999028fd5113e36","datavalue":{"value":"https://doi.org/10.1016/0095-8956(90)90061-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q2640608$1872B615-8B24-4232-83DF-CE60CA3A173A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f491637f199bddf4ec183462e8e70c857bd788e1","datavalue":{"value":"W2032344445","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640608$84D908E9-5E74-4566-A27C-DE0D3DE956A3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c40869f92f97b7b21fb8813ab0f54942dd226aff","datavalue":{"value":{"entity-type":"item","numeric-id":3222874,"id":"Q3222874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$DDF31B63-C509-4A20-8961-D686B4F9060A","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":"Q2640608$E5B6CC08-0473-44CC-9E37-05097A0A3C5F","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":"Q2640608$212F3841-0B4E-4516-ABDC-2B51DE6CB543","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":"Q2640608$A852035E-3059-4EC9-B27E-82A50C5A5F9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5ca62ac4085b233718cfb5d208930294245ea81","datavalue":{"value":{"entity-type":"item","numeric-id":5903367,"id":"Q5903367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640608$712DB10D-F03B-4EED-A2E6-ED2B7B1BD904","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":"Q2640608$67285246-0B78-47B3-B8E6-68ED6C09FC5B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5288865cb1b373564db09dac2662e7a69fbd33be","datavalue":{"value":{"entity-type":"item","numeric-id":4326544,"id":"Q4326544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a02abe2e6d8ff3df1e2b7feee87afa2ee1dae2cb","datavalue":{"value":{"amount":"+0.8586041331291199","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":"Q2640608$96121745-B6D7-4086-9351-C09DADBA39A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"845ea0bf368c0e89637e0990ba158ce439fdf582","datavalue":{"value":{"entity-type":"item","numeric-id":4883061,"id":"Q4883061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01274035bd7b05c68631ad7c88bafea7c5fd55f4","datavalue":{"value":{"amount":"+0.8476378321647644","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":"Q2640608$A34F4F81-F2B5-4282-B1C4-A3F23B6546DB","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":"40229f7a2b5103f5041e53f5d4b0b8d455da7693","datavalue":{"value":{"amount":"+0.8177271485328674","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":"Q2640608$8046E1CE-F55C-457B-BF9D-9EB5209420DC","rank":"normal"},{"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":"4c644a62ce14b967a5c77e515951add8989f843d","datavalue":{"value":{"amount":"+0.8131760358810425","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":"Q2640608$B4CAA4BE-4894-43FD-B443-F2B1F097F897","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":"a6e30f782f4c713baa124c259c53e786d26c5f71","datavalue":{"value":{"amount":"+0.8102640509605408","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":"Q2640608$27A87B3A-2531-4025-B4C4-980297C6F30F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2640608","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2640608"}}}}}