{"entities":{"Q678852":{"pageid":680701,"ns":120,"title":"Item:Q678852","lastrevid":63434226,"modified":"2026-04-11T13:07:42Z","type":"item","id":"Q678852","labels":{"en":{"language":"en","value":"Meyniel weakly triangulated graphs. I: Co-perfect orderability"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1004419"}},"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":"Q678852$76E0D276-CC27-4790-B91B-BC49436B6320","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cb88d0d422d770d92a71f5fcfa04d18c777f1e9e","datavalue":{"value":{"text":"Meyniel weakly triangulated graphs. I: Co-perfect orderability","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q678852$3EE3D5A8-2DD3-41A1-978D-200B55FF2FED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ea0beacdffd441a547f4e740b169afc509cca15","datavalue":{"value":"0878.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$CA1E31FD-ED6B-427A-A9ED-2134F86ABA06","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0b4b3c6a6825e7ca096f1c89d6064f971a285ed","datavalue":{"value":"10.1016/S0166-218X(96)00008-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$C8341D58-1285-48D2-8A6E-59E81FFEECFF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46bd635dd0821de2113c270b8d0c0de1c106ffb3","datavalue":{"value":{"entity-type":"item","numeric-id":222626,"id":"Q222626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$5594AB6B-678D-4A1D-8777-34CA0869CD4A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$502A333A-1618-4182-8A7D-51F150222221","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7373ca90e4b5d90975ef94cd3137f8d0492677d7","datavalue":{"value":{"time":"+1997-12-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q678852$2435A6B3-CD04-4D38-A260-24918D51F059","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q678852$26EFF0F8-D94C-45F7-8D1D-64EAB27F3D33","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cf174fd8d4acd32f6723b2a13ccefe5eb3271c00","datavalue":{"value":"An algorithm is given that finds for any \\(P_5\\)-free weakly triangulated graph a perfect order in polynomial time. This proves a well-known conjecture of Chv\u00e1tal that every \\(P_5\\)-free weakly triangulated graph is perfectly orderable. A graph is weakly triangulated if neither itself nor its complement contain a chordless cycle of length five or more. A graph is pefectly orderable if it has a perfect order, i.e. a linear order of the vertices such that for each induced ordered subgraph the number of colors used by the following greedy algorithm equals the chromatic number of the subgraph. The greedy algorithm is: given a linear order of the vertices of a graph, color the vertices in order, assigning to each the smallest positive integer (each integer representing a color) not assigned to any adjacent vertex already colored.","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$1681CE95-8572-41F4-BF99-6A527FF767FB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2499add345269c93c5ed1b650d8b90573cb6b1a8","datavalue":{"value":{"entity-type":"item","numeric-id":242846,"id":"Q242846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$D64D99BD-CAB6-49A9-9CE3-36572153B3B6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$4A9466FE-A44C-4A17-A7E4-32E6ADB40657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$F0F36599-F134-41F5-A03E-F543559553D4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"59cea12c16c0095efed4b1a49c7d12146c475955","datavalue":{"value":"1004419","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$A1C81DC3-F8C4-4A12-9CB6-28AE12471064","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"40f5464d7011aa5d406c15c16406937ac783c212","datavalue":{"value":"weakly triangulated graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$32EDA02F-B3C6-4E5C-933C-15F8EE712DBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a146dff6c120af7a8c6e0b50231d393b60d17a9e","datavalue":{"value":"perfect order","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$009B4456-B949-4D4B-A627-58B51B96DF70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69e1a15ffa6d96f89821f9d1c0b2940fa6fb1efc","datavalue":{"value":"conjecture of Chv\u00e1tal","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$1026AC08-A8BF-4E62-BBB1-0FF7D925A759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2533f2ca05f3690a52ae55af277ef80e615ccc20","datavalue":{"value":"pefectly orderable","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$49096B0E-3AE0-4F45-8BE6-ED92B25500AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$3E295291-4A14-4DDB-8E5F-8D3E5195A4C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q678852$A9BD7AD4-3806-4293-8486-2DE5FF266750","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":"Q678852$9F3DDE5A-5CE8-46EE-8D17-770F2E596A31","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b717ce5476163967b0df9674233704df8f3864c4","datavalue":{"value":{"entity-type":"item","numeric-id":3344216,"id":"Q3344216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$27167EEF-DFD3-4427-B280-EDB95340CEFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98d84d8d1a6e846802c9d13beeae73d688fdc4b4","datavalue":{"value":{"entity-type":"item","numeric-id":3356337,"id":"Q3356337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$F91AD6B4-6CA8-4123-A47C-2B8033C1BFE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$FF4A75C5-1190-4A02-A03E-83151B65197E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5631aef48ca73bba112645cb31945f3d8ff4b55","datavalue":{"value":{"entity-type":"item","numeric-id":1917290,"id":"Q1917290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$7912BADD-341B-4C39-B5D7-5F03AB9EC0D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbc1cbf254c6eb54db676c3af43bf0720c8750ac","datavalue":{"value":{"entity-type":"item","numeric-id":3798703,"id":"Q3798703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$0BFAB8B6-9F57-45F4-B41F-639FAD5FAE42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"caa0cfe5743ca696f656ded77f179f5be81c2db9","datavalue":{"value":{"entity-type":"item","numeric-id":1193431,"id":"Q1193431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$604E5F99-A600-4D7D-A9D7-063720350488","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":"Q678852$709755BF-E5DF-41B0-85B2-F0C4B6497980","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26b962d5ada8b5bb3c241cecf1e141991f1d8c34","datavalue":{"value":{"entity-type":"item","numeric-id":918707,"id":"Q918707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q678852$657FF5C8-4474-455C-9D0F-B2AA749E3FB1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d4ed698dfd6db20cc86c3188ceba7d38503d1fb2","datavalue":{"value":"W2043418908","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q678852$9A4C5178-C9AE-4395-B05D-E2288B77A9DC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b4b17e20dc229cbab9619b16f4d20f6de8bad46","datavalue":{"value":{"entity-type":"item","numeric-id":1193431,"id":"Q1193431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0217c24debb0a97103656a8d4717fb920345cd9b","datavalue":{"value":{"amount":"+0.8457682728767395","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":"Q678852$B3EF07E5-964F-47E4-9525-F77BD5160BA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10ae09667ceba9715d22199702e34348eab1cc42","datavalue":{"value":{"entity-type":"item","numeric-id":3800062,"id":"Q3800062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"056cbf794f937430623c50429d3e3e8e2a6ad343","datavalue":{"value":{"amount":"+0.8146802186965942","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":"Q678852$AA88E775-C984-49A3-8EC3-B337FE4C10D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48ac852cc6030418fdeadb8ecbc9359428cac294","datavalue":{"value":{"entity-type":"item","numeric-id":860461,"id":"Q860461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c410958829d3adc324fefa365ac4dfe68551f133","datavalue":{"value":{"amount":"+0.7953422665596008","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":"Q678852$4A787569-E620-4DAB-9DD1-571A0A03A80E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2d2bdba449d791cea672413b6afaa0e26101585","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83c005d3d2cd2397b19c04f50a8accd8e75bbf48","datavalue":{"value":{"amount":"+0.7907983064651489","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":"Q678852$CEC41CF0-F1D2-4824-BFA1-8FEDF7988E94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Meyniel weakly triangulated graphs. I: Co-perfect orderability","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Meyniel_weakly_triangulated_graphs._I:_Co-perfect_orderability"}}}}}