{"entities":{"Q2640612":{"pageid":2651355,"ns":120,"title":"Item:Q2640612","lastrevid":79437305,"modified":"2026-05-06T13:54:25Z","type":"item","id":"Q2640612","labels":{"en":{"language":"en","value":"Colouring series-parallel graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4187835"}},"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":"Q2640612$683BF12B-52F9-4399-BA5E-1EB72E102AAC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2b7226ccedcf09212983521a934c52ed208e8586","datavalue":{"value":{"text":"Colouring series-parallel graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2640612$7B64ECDB-6D45-41F9-99B8-79CEF26A5686","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"623e63ed4a4d65e3947dee7d2dd2c3a5ba264479","datavalue":{"value":"0721.05023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640612$9E6C2EBF-C63F-4AD3-A84C-A6AE4EF86CEE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9a838a54a88da313978eaeed6d934fec65bf71c4","datavalue":{"value":"10.1007/BF02128672","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640612$F6590FA8-02D1-44FF-839C-C479B31A8775","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$66D26080-77D7-4B0B-9CD6-F2EA2D07CFF8","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":"Q2640612$FF592408-E8AA-44A3-BFEB-FBC71692F45C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a55ed189be7f2c99ae0a78cd79533c27c01a68e8","datavalue":{"value":"The graphs under consideration are finite, and may have multiple edges but not loops. A graph is series parallel if it can be reduced to the null graph by repeated use of three operations:   (i) delete an edge parallel with another edge,    (ii) contract an edge incident with a vertex of valency 2, and not parallel with the second edge at this vertex,    (iii) delete a vertex of valency \\(\\leq 1.\\)     A first result concerns the chromatic index \\(\\chi '(G)\\) (the minimum number of colours of a proper edge colouring) of a series-parallel graph with maximum valency \\(\\leq k\\), such that \\(k\\cdot | X| -2| \\bar X| \\geq k\\) for every subset X of odd cardinality \\(| X|\\) of the vertex set. In this case \\(\\chi '(G)\\leq k\\) holds.    A second result is the proof of the correctness of a ``greedy algorithm'' for finding a vertex colouring of a series-parallel graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$A89FC5C7-9E60-49FC-85E5-23B238166F77","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640612$E324864A-60A0-42F0-9506-DA6FA0FB6081","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8069f61c55f6a5467fb401a4e79a9973358237c0","datavalue":{"value":"4187835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2640612$2D8FD461-5D74-4994-BE34-750E00A20133","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$96BAB032-E1FC-4FDB-849E-B08F0743A363","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$8EA8A734-0AF2-41AC-A373-3535015A1ADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be8df57be8c106df4fbe375ad2ff9851f149c079","datavalue":{"value":"colouring algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$19F6910C-3E1E-4373-B920-9E37239D0FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb191028560f8580185d25fb1e0694b4ee05dbf4","datavalue":{"value":"series-parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$E05977EC-BE0A-48C6-AD6E-D185755520F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a61866b28ef67a30472e3ee08657696fe272f4","datavalue":{"value":"vertex colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2640612$D4E39B1E-47EB-472C-864C-51EC23CBB6FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$A7F7B225-A7B8-40D8-BA77-D1126B747365","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e82f32c91e1eb0067a512f27a8cb077a4f29f958","datavalue":{"value":{"entity-type":"item","numeric-id":640843,"id":"Q640843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$B65BF098-5FFA-41B5-BFAF-E0A673E1640A","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":"Q2640612$5D3682D8-B384-4406-948F-991CA7AB15B8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"85cfa63f67ed3743ed6d983c37c02f4185c5f671","datavalue":{"value":{"entity-type":"item","numeric-id":5811782,"id":"Q5811782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$0E5FB74E-101A-4CF1-8061-4DBFEBA88D97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$390D1E19-303F-47D5-98E0-E2AFB099379F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$A6379F72-D537-464E-94B0-01CF10B612F5","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":"Q2640612$6FBB8CD8-93B0-4CF5-B5F2-8DE65ACC0871","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93b5dd3aaaa97e784ccc6acc1a567e057de94528","datavalue":{"value":{"entity-type":"item","numeric-id":3274170,"id":"Q3274170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$82A05F63-FE8A-4243-A539-773CA4CC2992","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$FF839013-0028-4468-9ECF-9028F709B577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ca254ff9c6e3ea71f0fe6a417e1e536023f31897","datavalue":{"value":{"entity-type":"item","numeric-id":1084107,"id":"Q1084107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$4395BDD2-9B96-41F3-9689-E81F3C1CF6AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d93131d3cdff5a369acc96e6fde7360525e3cc8","datavalue":{"value":{"entity-type":"item","numeric-id":1161527,"id":"Q1161527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$1BECFA10-801F-4083-AD75-5149BFA7B4BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2640612$91783C93-E981-4465-9887-0C5A759E1BEA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1142d1f604fa487384a088f1ebe1d71772445e70","datavalue":{"value":{"entity-type":"item","numeric-id":2704446,"id":"Q2704446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b72c40269da604a761fc62e5caf513f247c1e499","datavalue":{"value":{"amount":"+0.8754702210426331","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":"Q2640612$161933CC-9645-4577-85FD-5BFFE81A4F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6db60ef11a24d0b675cbb2a2dc0f84c67ed7a602","datavalue":{"value":{"entity-type":"item","numeric-id":1808155,"id":"Q1808155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2732dc5d1907af73dee45335100e1aaa89923ae0","datavalue":{"value":{"amount":"+0.8507397770881653","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":"Q2640612$48521A9A-70BD-4AEA-9181-B74D184D8B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3662fd98b188490ab0f78a107b9663e9a42d6fa6","datavalue":{"value":{"entity-type":"item","numeric-id":3418612,"id":"Q3418612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"34bb0ea471b1e179b8fdf168fc0bcaa4b7aa22c6","datavalue":{"value":{"amount":"+0.8256027698516846","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":"Q2640612$8AE35A89-BB3A-4B31-824C-E662EC2EDC8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2706452f43ff6301c34393d7a92e9031dab44dd","datavalue":{"value":{"entity-type":"item","numeric-id":4304340,"id":"Q4304340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30047124abff814e6c48ce24fddd774b647096b1","datavalue":{"value":{"amount":"+0.8228161931037903","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":"Q2640612$8130F965-39CF-4F1D-B3BF-95250B3D8BC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c6ac0cdd320fde49a85b1ebbe54ece997a9a452","datavalue":{"value":{"entity-type":"item","numeric-id":3466361,"id":"Q3466361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0877a819095dc0e9752a95404eee611e321b640","datavalue":{"value":{"amount":"+0.8219205141067505","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":"Q2640612$4E76C9C9-F025-4EFC-8183-AA2668855CEF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Colouring series-parallel graphs","badges":[]}}}}}