{"entities":{"Q1382811":{"pageid":1393551,"ns":120,"title":"Item:Q1382811","lastrevid":43070083,"modified":"2025-07-17T10:40:40Z","type":"item","id":"Q1382811","labels":{"en":{"language":"en","value":"An algorithm for coloring some perfect graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1130761"}},"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":"Q1382811$705B63FF-03B9-47CF-B969-FD912441CBA5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5b74fd589529facc9e81f698c3a689dc9955775a","datavalue":{"value":{"text":"An algorithm for coloring some perfect graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1382811$C40C03FE-4F7C-4FF3-BC3C-D27026364E3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47a23028b228f93ec98ce605a0334d56efda445b","datavalue":{"value":"0895.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382811$2B676B07-DEA7-4AB8-85AF-D28204BF29A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1125b6ba1e629503426d78f0255deeafd0fb4313","datavalue":{"value":"10.1016/S0012-365X(97)00082-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382811$BC602108-A27A-4D60-8E76-DF26CCBFD9C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"692ce2048991e39aaf8d5623dc50cd220956e79b","datavalue":{"value":{"entity-type":"item","numeric-id":189438,"id":"Q189438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$AB144061-D7DE-450D-B4DA-C27BDAB5E442","rank":"normal"},{"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":"Q1382811$C2D2E55E-3B6F-484E-9D0B-3C55226C006C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"60111ae794b7dba101c43e51600dac2730eee2da","datavalue":{"value":{"entity-type":"item","numeric-id":1126203,"id":"Q1126203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$1A79D22F-1118-47C4-9CDD-E1699D49F6ED","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":"Q1382811$0BBE9687-E4D8-49BE-9671-DB04629FA88A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1f4edbc315b46accf8681ddd2933c397936bf8c2","datavalue":{"value":{"time":"+1998-09-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1382811$8B49C35E-AAF5-4310-88E5-CDDE968E70BB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ac45d72b40e8fb7d8c998dff69fcaa921c8de13","datavalue":{"value":"A graph \\(G\\) is perfect if every induced subgraph \\(H\\) of \\(G\\) has chromatic number \\(\\chi(H)\\) equal to the size of a largest clique of \\(H\\). An algorithm for colouring a \\(K_4\\)-free perfect \\(n\\)-vertex graph \\(G\\) with \\(\\chi(G)\\) colours in \\(O(n^3)\\) time was presented in [\\textit{A. Tucker}, A reduction procedure for colouring perfect \\(K_4\\)-free graphs, J. Comb. Theory, Ser. B 43, No. 2, 151-172 (1987; Zbl 0634.05028)]. The present paper uses this algorithm to obtain an \\(O(n^4)\\)-time colouring algorithm for a larger class \\({\\mathcal G}\\) of perfect graphs: \\(G\\) is in \\({\\mathcal G}\\) if every induced subgraph has a vertex \\(v\\) whose neighbourhood \\(\\Gamma(v)\\) has property P4: the union of any four triangles of \\(\\Gamma(v)\\) contains a \\(K_4\\).   The paper presents an \\(O(n^6)\\)-time algorithm to test property P4; the time taken to test a graph \\(G\\) for membership in \\({\\mathcal G}\\) and to order its vertices \\(v_1, \\dots, v_n\\) so that \\(\\Gamma(v_i)\\) has property P4 in \\(G- \\{v_1, \\dots, v_{i-1}\\}\\) for each \\(i\\) (a necessary pre-processing step for the colouring algorithm) is not given. The paper mentions an algorithm for colouring any perfect graph [\\textit{M. Gr\u00f6tschel}, \\textit{L. Lov\u00e1sz}, and \\textit{A. Schrijver}, Polynomial algorithms for perfect graphs, Ann. Discrete Math. 21, 325-356 (1984; Zbl 0554.05041)] and states: ``their algorithm uses the ellipsoidal method and is not very efficient in practice.''   This reviewer would have liked to see a comparison of both the theoretical and experimental running times of the algorithm in [Gr\u00f6tschel et al., op. cit.] with the one in the paper under review including vertex ordering.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382811$9AC47F64-8580-4A17-8999-73C6A87A6272","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382811$91BFEE3E-874C-46B7-B1C1-149FCB8DC6F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382811$D0611CED-24D7-498C-A4D7-9657AAA5818D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c3ea86dc8777aebd504c4bff7349dd88e17d4f2d","datavalue":{"value":"1130761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1382811$E097F7FF-D037-42A2-80DA-F1154C775DA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382811$008CFCCF-0B4E-4F7C-ABD7-9ED074BCE264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59e104fc9083dc8c4e491b340ba5128d82bfc9b1","datavalue":{"value":"colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382811$92F10C57-7E44-4854-9AFC-1683E9BBE5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8df57be8c106df4fbe375ad2ff9851f149c079","datavalue":{"value":"colouring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382811$ACE26825-C48E-42B0-9DAB-779F741CC936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1382811$DBD4F848-E44B-4FE2-8A97-D96238220112","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":"Q1382811$71A9902B-6428-493E-BE4E-9D3EF97021FC","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":"Q1382811$09C1DB64-8D58-42E0-BD93-595317694DD8","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":"Q1382811$BC1C047C-2148-4F29-BAD6-E682E0CDD88C","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":"Q1382811$7DF102A3-8F6E-43D4-AD6A-51DBF637DF84","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":"Q1382811$0104EB6F-CC69-4C61-B3AC-DA14FE9B6140","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":"Q1382811$76A333A8-F800-46BA-85BF-758032852ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59dfb2bf34aa9412aae5438b884f8d1290678000","datavalue":{"value":{"entity-type":"item","numeric-id":1126205,"id":"Q1126205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$21A2BF19-084A-4715-9249-BE01665B2001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41cc6a286064615a5226bdd0939f0f85a946c13e","datavalue":{"value":{"entity-type":"item","numeric-id":1167741,"id":"Q1167741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$F16AF711-FA22-4A0E-892B-C8B578A5F6E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bba15cf4a9d2c986ffe8184ac3a6d051fff29cb","datavalue":{"value":{"entity-type":"item","numeric-id":3335007,"id":"Q3335007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$4C1787EB-0DD9-45BE-B52F-67384D329ED8","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":"Q1382811$CCADFEF9-E67F-477A-8DC1-629F021C4F33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85150cc05a7cb0438cfbcdc2c53832387bb028d7","datavalue":{"value":{"entity-type":"item","numeric-id":1096639,"id":"Q1096639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1382811$25BCB6A9-00BF-4CB1-BB8B-73165B83E6D3","rank":"normal"}],"P1643":[{"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":"2e7fb50962aa8bc926b05859268f0eaf249f19ca","datavalue":{"value":{"amount":"+0.8338427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$AEC1C8FC-90C6-4D23-9F49-9BE21F1E9D81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d23d9db45fe0d1dfd1a11626157bbe5b010ac109","datavalue":{"value":{"entity-type":"item","numeric-id":1071025,"id":"Q1071025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ac3f3ba0dabed936ec3706a5464ec7cb98799d4","datavalue":{"value":{"amount":"+0.83312684","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$599F0E84-7E29-430D-BAF3-EC96A2BDDF66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f82f1d58a378c5c11a10b3fe3cd8aab9c0bad226","datavalue":{"value":{"entity-type":"item","numeric-id":1096639,"id":"Q1096639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b80311d9810f43fae366d9157eab677408cfae88","datavalue":{"value":{"amount":"+0.8183938","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$4416C798-2745-49C5-9B6D-D6A20E66BC2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07fe971c0027f2a26325d89fa8632e9940790736","datavalue":{"value":{"entity-type":"item","numeric-id":1375694,"id":"Q1375694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76d127b9d6bac213fc7f5baa4788de2dbebe3d2e","datavalue":{"value":{"amount":"+0.81059146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$FF9A4CEE-B443-48F4-9919-D28F27791E11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86b6a6d0119309053b1634cb05e71c31082213d8","datavalue":{"value":{"entity-type":"item","numeric-id":4635984,"id":"Q4635984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8579adad3be031e509b8595259211605fa97a776","datavalue":{"value":{"amount":"+0.80779964","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$B49D5D34-CA7A-46F2-8B67-EA34D2C64E88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6360a9a0b464ae78d6393d5b83dc569c89d60033","datavalue":{"value":{"entity-type":"item","numeric-id":4024059,"id":"Q4024059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e692caaa2031cd92f7b4f1b1ef15c18fe1de88c","datavalue":{"value":{"amount":"+0.80706376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$5A7C17B3-F0F0-4235-BB15-B5F0B09B7D15","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":"88b0c35dda442c927e9ad508c847dd19d471d01d","datavalue":{"value":{"amount":"+0.8054662","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$7115D7DA-5BD4-41C6-9BFB-E389B0707463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2de8fdc5de3a5ec8c671ed464fe81507e83154e0","datavalue":{"value":{"entity-type":"item","numeric-id":3337488,"id":"Q3337488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31b4f268bd0693ea133e9a483d06e1ba46eb02e7","datavalue":{"value":{"amount":"+0.8033158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$B310B147-0964-4BD9-85E5-A6641CA8AB7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"703518aca3db3de5511e8b041b3a83b1f8d6ebee","datavalue":{"value":{"entity-type":"item","numeric-id":1944175,"id":"Q1944175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e981ae24ea7bfdc7b5648d983d41be775e04a355","datavalue":{"value":{"amount":"+0.79879105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$F14C419E-3F0E-4922-AA84-616E3563BB57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e908a1c344a44381e8c7b0b7f7533e02686b4478","datavalue":{"value":{"entity-type":"item","numeric-id":911763,"id":"Q911763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"75f7d4e880dfee2f19c50077f412ad2e3459c6b8","datavalue":{"value":{"amount":"+0.7948348","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1382811$2CFEC547-753E-4944-A145-D307FD134B73","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1382811","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1382811"}}}}}