{"entities":{"Q5959097":{"pageid":8135899,"ns":120,"title":"Item:Q5959097","lastrevid":47762863,"modified":"2026-01-02T15:21:28Z","type":"item","id":"Q5959097","labels":{"en":{"language":"en","value":"Consecutive colorings of the edges of general graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1722217"}},"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":"Q5959097$513F2C08-343B-4935-B27A-756CEC86C6C0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"252fb0a9ac88faeae4a7edc34a2ffc6fa3470650","datavalue":{"value":{"text":"Consecutive colorings of the edges of general graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5959097$7BA4A203-35E0-402C-B550-EEA02D4D96FC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1536b1a7e57a794f5fda5d33d1fac4d0b220b860","datavalue":{"value":"1007.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959097$C68A1C7F-9F17-45D4-8966-F7A96C6663A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0295ed66ae575a605c97077d004e75c4eec32300","datavalue":{"value":"10.1016/S0012-365X(00)00437-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959097$339014E8-26FC-48DA-9688-435624CD64BE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"df859106777b262ea1e16ccf8d0885099b524191","datavalue":{"value":{"entity-type":"item","numeric-id":177037,"id":"Q177037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959097$B9625A16-6DBB-47B5-AC04-CEBA6008BF38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2681750faeff29d5132b89d9392ae6736d25c7cd","datavalue":{"value":{"entity-type":"item","numeric-id":237429,"id":"Q237429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959097$9E5DAEFC-3168-45FF-A785-B632C9848F63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"681fa36f324bfdb5f85fc6878945cb77d35a0028","datavalue":{"value":{"entity-type":"item","numeric-id":237430,"id":"Q237430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959097$90A66D9C-0FA0-4E04-BDBE-DA8C78AFEA27","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":"Q5959097$2BD94A7B-6997-48F5-8D9C-F8F28CB78F3F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"231746dd1b162532443840a32e2f1ac3f5dc4bf7","datavalue":{"value":{"time":"+2002-07-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5959097$12410430-A09C-46BC-BEE1-E7DC2C4E52EB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0c7a2b26ddca1340dd49c775ee96656e6d1b5382","datavalue":{"value":"A consecutive (or interval) edge-coloring of a graph \\(G = (V, E)\\) is a map \\(f : E \\rightarrow \\mathbb{N}\\) such that the colors of edges at each vertex are distinct and form an interval of integers. It follows from the well-known NP-completenes result for edge-colorings that deciding whether a graph is consecutive edge-colorable is NP-complete. The authors then prove that for consecutive edge-colorable (triangle-free) graphs with \\(n \\geq 3\\) vertices, the maximum number of colors used in a consecutive edge-coloring is at most \\(2n - 4\\) (\\(n - 1\\), respectively). They further determine the minimum number of pendant edges to be attached to a cycle (a wheel, a complete graph) such that the resulting graph admits a consecutive edge-coloring.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$D4C56F41-0CEA-4832-A559-37294B1607F7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5959097$566AFE26-C1FC-4F2D-BC83-82BFF94B048F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959097$990F5919-6281-4D9B-B77A-A6673FE4CB5D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e0a09c69aabebbe622d1c1931499a5a172878d7","datavalue":{"value":"1722217","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959097$A72CD62E-ECC5-414B-8647-FBFE92E54B39","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f0f73cde5f3fcc0bbd11526e3f03ef30f4b8da7","datavalue":{"value":"consecutive coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$129F5860-5794-42BE-8610-5C4BA878170D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"788ec43786d127bf62e1bbf0b473c43a7c87ad23","datavalue":{"value":"interval coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$1A2BBD2E-8316-4F75-BF20-7ADC0B46634A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"de797320ce0a2184cca07f3061d8f9daa48cc061","datavalue":{"value":"chromatic index","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$54FD8402-C328-4B56-86FE-3F838F223BF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7f678844b43499cbef46e11738328c75fb0b5a8","datavalue":{"value":"deficiency","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$93018F14-4850-4C12-A516-76A748028CD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5959097$F642F7AE-7ABA-446E-A29D-40CA4E3DAADD","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":"Q5959097$F6349DFE-265B-489F-AED7-8C54A9B0CC02","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"12196cee2297f6836e2b383d42ac00780bfd9c8b","datavalue":{"value":"Q128018534","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5959097$9510932E-626D-42D4-B2AD-4CC0C763D0D8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65d6bab340f7b3d4082bd482eea81cbfaa6991fe","datavalue":{"value":{"entity-type":"item","numeric-id":4393386,"id":"Q4393386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"891895db9343ebfb21be179a50a3a27f91d9054e","datavalue":{"value":{"amount":"+0.8630841374397278","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":"Q5959097$6B4B94C4-7BB0-4AEC-9B21-93F497C3B1B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19190395ea6a900b2ec83776285403b842a0fab8","datavalue":{"value":{"entity-type":"item","numeric-id":658096,"id":"Q658096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0b8cbbdc56ecf3f10ccf5d413453f2b855e22ae","datavalue":{"value":{"amount":"+0.846312940120697","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":"Q5959097$E3DB6F62-D481-4F17-9E5A-5DD9C6D1E7B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e3e5673a0cbf80ec2f079761befa8f99de0d346","datavalue":{"value":{"entity-type":"item","numeric-id":3098089,"id":"Q3098089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfcc0441e7bcc51e8a999c9858e057accf08ba49","datavalue":{"value":{"amount":"+0.8313162326812744","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":"Q5959097$6032745C-8FA6-48E2-A810-152206630467","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6b609402b973d84fea4d81ae2985003419437c9","datavalue":{"value":{"entity-type":"item","numeric-id":1690222,"id":"Q1690222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce411a845a86e54cf1dc622e84674593fdb5beb7","datavalue":{"value":{"amount":"+0.8085954785346985","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":"Q5959097$CE778A6C-2D09-4F4D-82AA-628D2A294632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1c9f4c107394487fff5ec6f0f9b3a583dc3f056","datavalue":{"value":{"entity-type":"item","numeric-id":2457013,"id":"Q2457013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8071b41f3f35af6f069a7a117b5075f4be779245","datavalue":{"value":{"amount":"+0.8032822012901306","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":"Q5959097$9721D4EC-4A4A-473C-AE26-7E56CF3A5FBE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5959097","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5959097"}}}}}