{"entities":{"Q5916063":{"pageid":8032431,"ns":120,"title":"Item:Q5916063","lastrevid":93350144,"modified":"2026-06-05T04:15:25Z","type":"item","id":"Q5916063","labels":{"en":{"language":"en","value":"Chromatic index, treewidth and maximum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873182"}},"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":"Q5916063$D1CE99B2-B5E5-4022-B5F1-77872348D20C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4c4bff377f8699f4e4644267479bdbeae7df4fc","datavalue":{"value":{"text":"Chromatic index, treewidth and maximum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5916063$3EB97557-7DE3-4AD1-9AEF-0659616457B9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"806cde83cefd22418df9407ac3282e849c4cefb5","datavalue":{"value":"1391.05102","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$3F5EACFA-19E1-4DC1-A10A-EA072D5A46A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0dbf6af5287e9babdf9e28645d84a27e4a1d47d3","datavalue":{"value":{"entity-type":"item","numeric-id":289932,"id":"Q289932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$A8E1BE54-4157-497A-B3AA-BA47DFE71C30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"77d3e1f7cc67b64d7bc3cdbfa2b489bcff5356fe","datavalue":{"value":{"entity-type":"item","numeric-id":322294,"id":"Q322294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$B9C59522-1681-4C7A-A848-DCE3B800018D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ade5b253c80ba39315ecedaea21767e5440403a2","datavalue":{"value":{"entity-type":"item","numeric-id":293636,"id":"Q293636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$C4C81BFA-83EF-4EB7-A817-6B03E57B3A38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$3F087A5C-3055-4D0C-826D-B0343D3C8DDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5916063$2EE6FF53-115F-4E2A-8863-DCB100BAFF3C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b038a18e7a60901651e716d6a7a4684a372e51ba","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p23","type":"string"},"datatype":"url"},"type":"statement","id":"Q5916063$7433D2B8-310E-423B-99D7-3605702BF6BE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7c531beb527ddff2ab58e61e5919f2a27cf4c1ff","datavalue":{"value":"Summary: We conjecture that any graph \\(G\\) with treewidth \\(k\\) and maximum degree \\(\\Delta(G)\\geq k + \\sqrt{k}\\) satisfies \\(\\chi'(G)=\\Delta(G)\\). In support of the conjecture we prove its fractional version. We also show that any graph \\(G\\) with treewidth \\(k\\geq 4\\) and maximum degree \\(2k-1\\) satisfies \\(\\chi'(G)=\\Delta(G)\\), extending an old result of Vizing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5916063$2B7784B4-2E36-477F-8208-AA2F43E796A4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$D3AB8EB1-3DDB-4D68-ABD5-229F55B4FE68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d765cc4b218ae225bb23e4f50aa85c5b7550ef66","datavalue":{"value":"05C72","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$5183334D-D501-4B0E-9D40-E07BF5287D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$190C4C1F-EBCD-4BEE-B516-0BAD5E240415","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2f700c51af14ad442a6cb065e949048daa8c973d","datavalue":{"value":"6873182","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$1E89C349-7377-482F-BF6F-44801ACF2C68","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q5916063$2211DE30-F467-48EA-834F-99AA7EE57C84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e3d58b5f68ae7d6337620e7d25da0081273ed23","datavalue":{"value":"edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5916063$214C24DF-1A95-4040-8A83-9E5503CAAE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2710ba3d2566731331c74df8dd12ba33cf580ac9","datavalue":{"value":"fractional edge colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5916063$0924866B-B6DE-4D49-8B84-166CC66DE86B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q5916063$DDC7662E-1550-4AC2-AE9D-B166F9E0E036","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":"Q5916063$C01F9875-00EA-4CAE-9A1B-7B31868528AB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"57515aea1ad564d767f2a1d2b4fdb04b8bf50ff4","datavalue":{"value":{"entity-type":"item","numeric-id":1274912,"id":"Q1274912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$CC49CA14-FDB2-47B2-91AD-DDF50D25A56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8b23be685b19bdd0313eaaa79ce5140147fe55","datavalue":{"value":{"entity-type":"item","numeric-id":1366604,"id":"Q1366604"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$6B4E6C7E-643D-4AE8-9938-68CE0803C643","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bad700e9c03c09fecd3e4468848f2c06ba1c296","datavalue":{"value":{"entity-type":"item","numeric-id":4355071,"id":"Q4355071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$3528047A-F89A-40DC-80D1-2C715E307151","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9353124ad05795747eb02324818de1c65507abd9","datavalue":{"value":{"entity-type":"item","numeric-id":2800543,"id":"Q2800543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$0129CE72-6BA9-4126-9E35-207B660E0D3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41ab95cfd69e10430c9e72fb53fae7f5a4250a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4947393,"id":"Q4947393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$BE1A1DE7-CD78-443E-B1CB-96684323B3C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b11619a2fdb2060ffa8e3ea1e139344e1615e32","datavalue":{"value":{"entity-type":"item","numeric-id":3287781,"id":"Q3287781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$C130D256-9AC0-43EE-827D-21105FEC525F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62f9ac8959a316d9d6224cee5e5b68d63b6eaa5","datavalue":{"value":{"entity-type":"item","numeric-id":3118960,"id":"Q3118960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$9EF65368-C970-4275-B14D-5FFF0C4F2421","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":"Q5916063$28041051-5C27-4912-9F53-4A784D2D8712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d1d35de32e28bfba83587fdaec5dadbc65d8926","datavalue":{"value":{"entity-type":"item","numeric-id":2460621,"id":"Q2460621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$CC685007-BFD0-40D1-93A8-14410790AA1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3de609db001f545ec80139fa652f625e6b9d506c","datavalue":{"value":{"entity-type":"item","numeric-id":1808155,"id":"Q1808155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$55449163-AA97-47C1-A5F9-1F9B93121AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e76d15f0e9844553eca361034c3e508123e3ba11","datavalue":{"value":{"entity-type":"item","numeric-id":1844861,"id":"Q1844861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$DCD683FB-BA1C-4DC0-9085-AAEE3A06AC86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4002661922cfbf3b51612e8c6c4804f79fd6bac7","datavalue":{"value":{"entity-type":"item","numeric-id":1850561,"id":"Q1850561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$C4080B88-C4B7-4D4F-B23F-BD9C86DB2AA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c01149a6900c0f611a509645affd60c9a396109","datavalue":{"value":{"entity-type":"item","numeric-id":1854113,"id":"Q1854113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$EC2FBB56-3695-4339-B63A-F5EDF8CDECF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87c8ff4fc6f711a607a536b6572a8daeb1f68437","datavalue":{"value":{"entity-type":"item","numeric-id":5558480,"id":"Q5558480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$1493FEDE-8196-40C6-B265-032CA366BC0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f6e29cd4636c84e1b5c7e3136079d5f55ac9ec","datavalue":{"value":{"entity-type":"item","numeric-id":5935607,"id":"Q5935607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$D165304D-4097-48A8-9E6C-AF4CCA6D5C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"626d65a940351db2008e127c034b532252f3a4e2","datavalue":{"value":{"entity-type":"item","numeric-id":3837389,"id":"Q3837389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5916063$2A1E712E-C1C9-4387-A44D-7855CE79A5EF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f8a15a01e9668de06a50ab6160d9ac9b32e57d6f","datavalue":{"value":"bafkreiefewvfgnymlsyjrbjubxslw6hemx75j6mh2wyy534cd6ffddqwba","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5916063$C663F511-A572-47CD-B5DF-23B090429239","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28b73baceaafe75c4a5b404a2529a3cf414350b4","datavalue":{"value":{"entity-type":"item","numeric-id":5892299,"id":"Q5892299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"624dfb823099ff26bf4052787452744c9b5b215d","datavalue":{"value":{"amount":"+0.9831262230873108","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":"Q5916063$59FFA602-C903-4C21-87FC-7F3D7050EE4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77ba5ef39357d4039587455aab0e4c9bd413f042","datavalue":{"value":{"entity-type":"item","numeric-id":2800543,"id":"Q2800543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebfbb3c6b1be78f371a0606107da1291004af8c8","datavalue":{"value":{"amount":"+0.8459076285362244","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":"Q5916063$EFE532A1-0C9F-49B3-9CD5-B60E8FCF7D84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"028ea10e511108e3b4f2fff4b1b0724ba310cb91","datavalue":{"value":{"entity-type":"item","numeric-id":1748268,"id":"Q1748268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f156c6c0ed68901bcea244a7666485be908b56b","datavalue":{"value":{"amount":"+0.8239051103591919","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":"Q5916063$21EBA982-F3F8-40CA-BC31-AF7B3AB2304A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c831c70be6b2773d0bdfff6a3b8e36087caf7bd2","datavalue":{"value":{"entity-type":"item","numeric-id":752723,"id":"Q752723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e34f6ddd45cf69960aa8a5a4313e3c861a884a2","datavalue":{"value":{"amount":"+0.8176632523536682","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":"Q5916063$32416266-F468-42DB-9CE4-DCCC0F73BACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b8b3d7985b4db256e76e46d5cb123a51c655311","datavalue":{"value":{"entity-type":"item","numeric-id":6094039,"id":"Q6094039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30d8e6e61b7785885a98eb4364ffe47b927e45be","datavalue":{"value":{"amount":"+0.8155713677406311","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":"Q5916063$403353FA-2E4F-4729-A106-EF7C677A36AC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Chromatic index, treewidth and maximum degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Chromatic_index,_treewidth_and_maximum_degree"}}}}}