{"entities":{"Q964478":{"pageid":966326,"ns":120,"title":"Item:Q964478","lastrevid":65683080,"modified":"2026-04-12T04:18:32Z","type":"item","id":"Q964478","labels":{"en":{"language":"en","value":"On the maximum \\(q\\)-colourable induced subgraph problem in perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5693411"}},"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":"Q964478$9391273A-0BCB-40C1-B1C5-066A0EB2F0ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"711e8016b3bf6d83a069d8be978b3e53cc83770e","datavalue":{"value":{"text":"On the maximum \\(q\\)-colourable induced subgraph problem in perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q964478$4C893659-848B-4277-A7DC-A99589ADC77D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"49fd515f3d6aa0f444563805e67d9a39fa7fa4ce","datavalue":{"value":"1205.05081","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964478$E671D833-191A-4B6A-8B35-0062090A3CE4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"94c70d2757b3e467a0fccc07bcb509fe2dd1e2d0","datavalue":{"value":"10.1504/IJMOR.2010.029686","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964478$29061F74-709A-44CC-921A-9562F5DBDEAC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae9c63dad3e3cebbed817cbd57666403c4f55af7","datavalue":{"value":{"entity-type":"item","numeric-id":964477,"id":"Q964477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964478$4932BFBE-6A10-4F55-A947-F830D62C0043","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2cdd1892625a16441d3991f7370b427d06f9bb5","datavalue":{"value":{"entity-type":"item","numeric-id":190512,"id":"Q190512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964478$B6F6C313-08E6-42DD-8E05-AB2B2D414B67","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"08904a7410b5f731fa63153720439160d216b374","datavalue":{"value":{"entity-type":"item","numeric-id":548461,"id":"Q548461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q964478$BA2A9CB0-5C57-4F23-805E-A302BA2D80A9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"35759f2c57e380463f3872b667008da8bd531cd4","datavalue":{"value":{"time":"+2010-04-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q964478$F63C8C11-D7A3-44FB-88AE-1DE47C7565E6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8ed464844f338dc3af6e526e0706dca8f8386eb6","datavalue":{"value":"Summary: Given a non-negative integer \\(q\\), the maximum \\(q\\)-colourable induced subgraph (MCS) problem asks for an induced subgraph of maximum order among those that are \\(q\\)-colourable. By a result of \\textit{M. Yannakakis} and \\textit{F. Gavril} [``The maximum k-colorable subgraph problem for chordal graphs,'' Inf. Process. Lett. 24, 133--137 (1987; Zbl 0653.68070)] and independently of \\textit{D.G. Corneil} and \\textit{J. Fonlupt} [``The complexity of generalized clique covering,'' Discrete Appl. Math. 22, No.\\,2, 109--118 (1989; Zbl 0685.68046)], the MCS is NP-Complete even if restricted to the class of split graphs. In this paper, we investigate the approximability of the MCS problem in the class of perfect graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$EA3F8B00-996C-4136-8CCA-10EA7EAA9153","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964478$797C9176-7E42-4FE7-B846-14AA12E2B8CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0b24cd4df053ec75df1e7e9e00bdb694ad32d9a","datavalue":{"value":"5693411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q964478$7EE72087-8F5A-4783-AF3D-1DB4A5D047F5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1fc0d7b4e0514313bef02080965517bcc5ef461","datavalue":{"value":"greedy algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$99DC6B26-1F23-427C-94F7-49500AC44BA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$11F70EF9-47C5-4400-BA93-E222683E385A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a61866b28ef67a30472e3ee08657696fe272f4","datavalue":{"value":"vertex colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$5689BEE0-1256-43C4-886E-B30D8C8BDC3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"642186a0317dd29ba8808bff6fac4f9aaffd4440","datavalue":{"value":"q-colourable","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$DD83CAFB-938E-49A8-A917-44F411FFB165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e7aa9261afd174c3e2f5b7f5c7e2a299a554644","datavalue":{"value":"subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q964478$86899A81-3D42-49CF-8143-8FEC2F5092C9","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":"Q964478$844EAD53-3858-4AFC-8ADA-95CB72B1ACF6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ebe1e6bd34c0111f5b31fa9f5e60b7329529a49","datavalue":{"value":{"entity-type":"item","numeric-id":1755775,"id":"Q1755775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7d040b9ced7b2c4a1287ec4e8a650e406735e7a","datavalue":{"value":{"amount":"+0.8432936072349548","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":"Q964478$516D9694-9A68-408E-9508-05044A3E9E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382e5e936b64cdde8dff44a36586470c4db4dab7","datavalue":{"value":{"entity-type":"item","numeric-id":2864316,"id":"Q2864316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"649a23df9f386723dbc09ec98e2cf673be041b22","datavalue":{"value":{"amount":"+0.8381651639938354","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":"Q964478$A89306D6-3EAE-45F7-BA8A-5451C1749EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"307994403a9d068f26afeba8ff9f6f67a40c3b47","datavalue":{"value":{"entity-type":"item","numeric-id":4871128,"id":"Q4871128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c9bfd37b4fe195dc86996e36b91bbbb86f302c7","datavalue":{"value":{"amount":"+0.7713192105293274","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":"Q964478$7A9F6071-6EA1-409D-9E79-6D19973AD115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35bda9184e26b8b5b5fdc6a0bcaf00ae06945530","datavalue":{"value":{"entity-type":"item","numeric-id":3137171,"id":"Q3137171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9df949ecfe75de4af77527514fd9bea3ab490bcd","datavalue":{"value":{"amount":"+0.7683758735656738","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":"Q964478$0DE13C6D-FA00-4A47-8C93-9AA9EBA3F133","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":"9692af66acf45af049160eb04cb21617b6cc09b5","datavalue":{"value":{"amount":"+0.76426762342453","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":"Q964478$84E1CB88-892D-4396-BBE8-AA4B223674E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the maximum \\(q\\)-colourable induced subgraph problem in perfect graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_maximum_%5C(q%5C)-colourable_induced_subgraph_problem_in_perfect_graphs"}}}}}