{"entities":{"Q1111563":{"pageid":1122312,"ns":120,"title":"Item:Q1111563","lastrevid":49220887,"modified":"2026-01-06T19:17:24Z","type":"item","id":"Q1111563","labels":{"en":{"language":"en","value":"A fast algorithm for coloring Meyniel graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4075091"}},"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":"Q1111563$4CC217F7-EC0F-423D-AECE-921E11FDB107","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5a05795703ee687d22b6c7480be0d86723d6671d","datavalue":{"value":{"text":"A fast algorithm for coloring Meyniel graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111563$8297403E-219E-4408-975C-93F2E4550FD3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da06e0385c221226cef26b59d8aaf538658703c7","datavalue":{"value":"0658.05027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$06BBD24D-19B5-4EFC-BFD9-B78D49056B03","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1a2b4194ed98c9a0170082bf6069b181160fdca3","datavalue":{"value":"10.1016/0095-8956(90)90078-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$E479F359-60D4-475C-9699-F48AFC8C2AE7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$F45CE1BE-EDB0-4FD9-A6E5-FF05F9CE415F","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":"Q1111563$D3427A8C-E37F-43B2-A0CA-7C9064885CE5","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":"Q1111563$B79A65B5-DA8A-477F-9F8F-79F5E3133FC6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe4d2fcec9366d55b37fb5fdbbd366d2cff54393","datavalue":{"value":"We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph.    We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This \\(O(n^ 3)\\) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Ho\u00e0ng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$37D8CAC7-1909-4520-A60A-B7326CADF981","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$383DA202-8426-4D53-B4DE-08F888746D38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$F5670073-75BB-4185-A7C3-16E4DF439332","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$9A80E51C-6221-4576-A569-3C7AB00E7EE4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"55be1cc5614c7c6df56da6cd5516295f8083b071","datavalue":{"value":"4075091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$B5C16C34-64DA-4C55-A7FB-B51E1B21A4D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$5AC3C11C-0D17-4BFD-832D-3037573E960A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad953c972dffaf55600680cb93d5c1f4085c4b91","datavalue":{"value":"perfect graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$F81E21E3-CDE8-4D93-987F-4E38AE807DF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$39779FEF-699D-42EF-BA90-546ED1C3E5C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b5e5336cab30e039ac622a0d2dff0f49409a421","datavalue":{"value":"minimum coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$2161F27A-D4DB-4DCE-9621-D75020C9386C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"44a181c7b2997b4e3846dd20fd7f7cfe8269ff11","datavalue":{"value":"maximum clique","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$F86FDF23-C63B-4E6C-8ED4-B3598B6F2410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"090c2c0b1d99470e564b652f211e617415fe434a","datavalue":{"value":"Meyniel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111563$20E75504-EAED-43E6-81F5-2A9B44C225CB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"48d655289aa5d2135ce97cf03e76cbe770634bc8","datavalue":{"value":"Q56430115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$7DB3A7E4-E396-42D7-AD27-194FF42DC13A","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":"Q1111563$229A8DA8-87C0-4597-8B74-27B903334DB6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$011DC026-BBCE-4634-A585-CDB2EB0E8129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2d67bd3980ca4eba682fae6d5244771f4d9299e","datavalue":{"value":{"entity-type":"item","numeric-id":3222875,"id":"Q3222875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$B0689A9B-99F3-49E3-A444-7207298BB145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d899f6b1855af95c800659af2e7a6e0748e025b","datavalue":{"value":{"entity-type":"item","numeric-id":803147,"id":"Q803147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$85782DD1-CFD4-4A7C-A1E6-291F5E134B5F","rank":"normal"},{"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":"Q1111563$882CF5A6-4E54-4FB6-A767-8EE56D3A0D77","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":"Q1111563$8A893569-ABA3-4B00-BA06-E1D1565CCEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"493b9c7b82f10ace40363dca412120e379dc666c","datavalue":{"value":{"entity-type":"item","numeric-id":1095159,"id":"Q1095159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$AFF65A03-19B8-41A9-8E9B-77105E2E9D04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"848565b0c2025ab3a53b83ed30a366727997e5e9","datavalue":{"value":{"entity-type":"item","numeric-id":1096652,"id":"Q1096652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$27523A09-92DC-4C15-B7B0-595F44CFCD9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4ecc018fdb7c46440581e7f9a880e328ca21441","datavalue":{"value":{"entity-type":"item","numeric-id":1248633,"id":"Q1248633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$AFE77B66-B80B-47DA-90A2-EF1090B5B38D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"acb00d0ec70611e37f1f9b7aa90a17fd2c65931b","datavalue":{"value":{"entity-type":"item","numeric-id":3682511,"id":"Q3682511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$485213D4-0DD8-47C9-BD86-A42AC0DC681F","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":"Q1111563$4D8D6658-B2A9-4973-B50B-6F0E103AB867","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"248a7504bb8fe368192eba8244a37246499a14fd","datavalue":{"value":{"entity-type":"item","numeric-id":3714102,"id":"Q3714102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$F43C0D3F-1090-4903-8915-5C7D69297118","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54dec574b0c5e7327d705b995c5ee1dd4628ec94","datavalue":{"value":{"entity-type":"item","numeric-id":1171076,"id":"Q1171076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$CFE1DCC4-2133-408C-B0EE-877701C9955A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d118798912afc9fa343a1feb2c1381946ea1b062","datavalue":{"value":{"entity-type":"item","numeric-id":3686753,"id":"Q3686753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111563$806EFCD9-3661-47FA-9FEF-395D6955049A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26337547ac5f704ccb9f5b5d05829ccd97f58691","datavalue":{"value":"https://doi.org/10.1016/0095-8956(90)90078-e","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111563$BFA55470-8D6D-41E3-81C7-4D58BEE8856E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"583d93472ba5ef462e920f69eb8e6e7549a5cab1","datavalue":{"value":"W2013879243","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$31B81681-EAF8-45BC-B2B1-207E31C2C038","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"9f15b40cb0c4d55f69c244fa3ac7361cedf7c4da","datavalue":{"value":"journals/jct/Hertz90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111563$ABCCA9C6-7700-4385-A52C-6759192E4994","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41a60ce723c640d45ef8f225a094786edc49853c","datavalue":{"value":{"entity-type":"item","numeric-id":5937923,"id":"Q5937923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5295c9e0187e9862e7c96bd08913b4d6f94e4f9c","datavalue":{"value":{"amount":"+0.9009938836097716","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":"Q1111563$040B49D4-0BA7-47BE-B5F5-082B0167C346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29ff0ee996969fdfb76854465555a60992b78e76","datavalue":{"value":{"entity-type":"item","numeric-id":4346747,"id":"Q4346747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02bbef418acc2930ee2694049504beaf4a8db4d7","datavalue":{"value":{"amount":"+0.900993824005127","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":"Q1111563$E0A5ECAA-AD0A-4095-88C6-5D7B4D7D6E3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9788b65990a99b4cfd9e68a1fc75b8d6f2812f87","datavalue":{"value":{"entity-type":"item","numeric-id":3439304,"id":"Q3439304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"150bcd75ac7960ab5a0f6b8b6077ce307062be21","datavalue":{"value":{"amount":"+0.8878495693206787","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":"Q1111563$4BCB9711-25D6-4D76-9C0C-AFDCEBB53756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f0fb8deb77b7761d6f7659dc8e6e880d5f2c0b0","datavalue":{"value":{"entity-type":"item","numeric-id":5248996,"id":"Q5248996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ae8180099f23ba48351dfb1869c5f67a3dafde0","datavalue":{"value":{"amount":"+0.8445003032684326","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":"Q1111563$D4DA18C9-5973-49E8-82E3-EFBADAA220A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94af3bb923ce7c93d78c69e7158667999033a2fb","datavalue":{"value":{"entity-type":"item","numeric-id":1096652,"id":"Q1096652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da5a0d5d865ffcea63b431052e8cb65811fd9865","datavalue":{"value":{"amount":"+0.8340643048286438","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":"Q1111563$BE0041E1-9E6A-4DE6-8512-124AD899BDBA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111563","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111563"}}}}}