{"entities":{"Q2631073":{"pageid":2641816,"ns":120,"title":"Item:Q2631073","lastrevid":44529051,"modified":"2025-11-23T14:40:45Z","type":"item","id":"Q2631073","labels":{"en":{"language":"en","value":"Edge-colorings of 4-regular graphs with the minimum number of palettes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6607371"}},"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":"Q2631073$F95B66D1-FE83-4684-A3F1-8D14D7A20259","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1a03c5e421aab4e9980937412231ae8bbb1dd02","datavalue":{"value":{"text":"Edge-colorings of 4-regular graphs with the minimum number of palettes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2631073$7B0F3360-73D3-478A-9C1C-4CCF368A0D80","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b4393aef2389ff9701541ff4a2630d4f1880b95b","datavalue":{"value":"1345.05025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$87BDD563-BBF4-4525-84A7-2B3CF907650D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e3e5eb88cb46e6b4a80741b2023a7c7ec642ee6a","datavalue":{"value":{"entity-type":"item","numeric-id":663466,"id":"Q663466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$1CB96F78-F7A2-43FE-AF9D-B209BD70B609","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"39c4163d00db19bed4405f38e5a94302027e100f","datavalue":{"value":{"entity-type":"item","numeric-id":322187,"id":"Q322187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$1A5ABA5F-474C-4915-9315-F8BC71EE4B00","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$6D9EE5FC-147E-4E34-89B5-BA77027FCBA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"983499d539ab43bbb6f5e5531bc62eb931d87235","datavalue":{"value":{"time":"+2016-07-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2631073$E040BF5F-6AB7-4547-A93D-6B893861E041","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9bf8fa1c908c88a5f446fca08d02a7e21c3cca63","datavalue":{"value":"http://hdl.handle.net/11380/1102906","type":"string"},"datatype":"url"},"type":"statement","id":"Q2631073$20C9B7A4-0285-4678-9DE3-A1A5B1A8ED59","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"34a700708381f32e4826912e203c1060674dcc34","datavalue":{"value":"Every proper edge-coloring of a graph \\(G\\) induces for each vertex \\(v\\) a palette of colors, that is, the set of colors used on the edges incident to \\(v\\). The authors study the palette index \\(\\check{s}(G)\\) of a graph \\(G\\), defined as the minimum number of distinct palettes taken over all proper edge-colorings of \\(G\\), a parameter introduced in [\\textit{M. Hor\u0148\u00e1k} et al., Graphs Comb. 30, No. 3, 619--626 (2014; Zbl 1291.05066)].   Since the chromatic index of any graph \\(G\\) with maximum degree \\(\\Delta(G)\\) is either \\(\\Delta(G)\\) or \\(\\Delta(G)+1\\), the inequalities \\(1\\leq\\check{s}(G)\\leq d+1\\) hold for every \\(d\\)-regular graph \\(G\\), with \\(\\check{s}(G)=1\\) if and only \\(G\\) is class 1. Moreover, it was proved in the above-mentionned paper that the palette index of a regular graph is different from 2. Therefore, \\(3\\leq\\check{s}(G)\\leq d+1\\) whenever \\(G\\) is a class 2 \\(d\\)-regular graph. A natural question is then to determine whether this upper bound is tight or not for every \\(d\\). The answer is positive when \\(d=2\\) or \\(3\\), as an odd cycle and a cubic graph with no perfect matching clearly have palette index 3 and 4, respectively.  In this paper, the authors prove that the answer to this question is positive for \\(d=4\\). They also study \\(4\\)-regular graphs with palette index 3 or 4.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$DD8179F9-617D-4EFF-A524-CCDE9972EA24","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$D1A169E5-356B-4FCE-898D-772E4530DFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$A67EFED0-B152-44C1-921E-5997A3BAD6F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4465f4ff7edf1c2dc04cba874fedd303e0e5104c","datavalue":{"value":"6607371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$AB49B513-4707-4772-8926-A2B8EAD072AF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76b2b78428d8f4f88266d559678169d726e29643","datavalue":{"value":"palette index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$C7799B65-48B7-4939-9D4C-6CD07E79AA32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7960dc8c2d9dfdd702a5a50775b439700098ff97","datavalue":{"value":"4-regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$8E59299E-0E56-45B0-9E3F-F8069BC61879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$5DF023F8-DEC4-4819-95B7-A30E591F1795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"faccb3dd27d455effe5c8d86111e4907901be3d4","datavalue":{"value":"even cycle decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$7A698066-DD95-48ED-9C5F-A3429D6E9311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a816974a3ff22cc110ca78ffcd7b55e819e9c929","datavalue":{"value":"even 2-factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q2631073$BE04170D-4DA0-4923-B033-80AF3FC8F13D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"979cc330ddee08ebeac09e4443a54d002835fa71","datavalue":{"value":{"entity-type":"item","numeric-id":175612,"id":"Q175612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$F74946EB-5043-472C-9363-E8D88DD71994","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":"Q2631073$345755D5-FFF6-4512-97DE-A8B43555C14F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99cdb52df180a9cc6321eda3f5121b55e50b368f","datavalue":{"value":"W2253311773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$B88AD08C-46AB-4B50-9AA7-9D8AEE41B789","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$A7B086B2-DABD-4187-93E2-E9F043F67A3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a3a909228ea73bb377be0cc92c41214b1cd5b52","datavalue":{"value":{"entity-type":"item","numeric-id":4362092,"id":"Q4362092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$760574B9-5725-4BD4-BA77-44D849596491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1ed803bdecba4facba55cb7d393ee8962165858","datavalue":{"value":{"entity-type":"item","numeric-id":1074595,"id":"Q1074595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$2BA11BC9-3945-4FD6-9596-5C35BFCDE663","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"321093de9eba68d5d412b99a9bf101d6712e0221","datavalue":{"value":{"entity-type":"item","numeric-id":855303,"id":"Q855303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$7D89BC29-DB0F-4FEF-A6FE-ABF7113C14C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed0c220eb94954ecc2ec5bb2560393a078479712","datavalue":{"value":{"entity-type":"item","numeric-id":2014713,"id":"Q2014713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$F899D7A3-418E-4D11-B05E-18984448336D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ccc41cbbf9f8e558b79a23ca5d893c54a3b5a4ad","datavalue":{"value":{"entity-type":"item","numeric-id":2565689,"id":"Q2565689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$35A245DE-6A22-4EAA-8F87-57F1EE42A236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8658456c122ea10055a1fc45bac23690e56d6e4d","datavalue":{"value":{"entity-type":"item","numeric-id":442390,"id":"Q442390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$D2181696-103A-4140-99F0-54D4EBA0E9C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12f549aa36a86e2bcfdee370a9c7b275278942f0","datavalue":{"value":{"entity-type":"item","numeric-id":4286301,"id":"Q4286301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2631073$693C5BF5-4EF4-4EAD-8DAA-273A6A849C77","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"197d74a5dce3e51583bbcfcf5111465d94d9d195","datavalue":{"value":"10.1007/S00373-015-1658-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2631073$E249E2F0-DD71-4D97-8797-68E4906CCB2D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5fce010c6334fd157e8d62e84abaa47c4d4b1ee","datavalue":{"value":{"entity-type":"item","numeric-id":2113372,"id":"Q2113372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f8808434385b36ed2f9601198b63a0f37d3a28a","datavalue":{"value":{"amount":"+0.89899427","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$A75357D3-D670-479C-9BE7-4E5265D8B6C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bbc01bc1de8a9c0cd416d36d40188a824251c59","datavalue":{"value":{"entity-type":"item","numeric-id":5354847,"id":"Q5354847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fda3efcb4caefbdd1cfd6783124ff25e08187e26","datavalue":{"value":{"amount":"+0.86616653","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$09D1E336-012C-4983-A037-FF6B0E5DFA3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b5ee78a461f50870458c091385d6bf26b6acff6","datavalue":{"value":{"entity-type":"item","numeric-id":5377233,"id":"Q5377233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d02b385d8fd7c6b7f5f4811ef038de0b10278c0e","datavalue":{"value":{"amount":"+0.85159945","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$882B2953-7920-46EA-ABAE-082D1A46BB02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1bde5b6665fb7c2f8876dc237fc49cda2b9e2c25","datavalue":{"value":{"entity-type":"item","numeric-id":5239936,"id":"Q5239936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2d620e01dd70be0ca386069b2a021bc06f1987a","datavalue":{"value":{"amount":"+0.83794224","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$F774D5FC-CB14-4E9A-8BC9-B8129168D242","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bad55d7fecd399eb61d995e0c6da6ea9a1243c7e","datavalue":{"value":{"entity-type":"item","numeric-id":5068489,"id":"Q5068489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"732c4e175bf675779d10a13454747181cc7aaf1e","datavalue":{"value":{"amount":"+0.81208825","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$AD06E485-4DA5-48F6-9648-7D2C348AAEC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16489564fbc08472cc77fa72e7b94ba568f9d65e","datavalue":{"value":{"entity-type":"item","numeric-id":5217064,"id":"Q5217064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33794d246390a03c045191c49e6ce0aee019f92e","datavalue":{"value":{"amount":"+0.8092101","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$1C726CB7-9F1E-4089-9751-BD52BA5A21C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"506ec8f0f56a4d76a1b2dc31d247d69302ea5898","datavalue":{"value":{"entity-type":"item","numeric-id":2014713,"id":"Q2014713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9e2195dec431c91c546d038275b8d4d7860498c","datavalue":{"value":{"amount":"+0.8088183","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$15CACAFE-59D6-4145-A698-0FECCD963DCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ce112edc0bf4ab9e3250e9e703b561620a67846","datavalue":{"value":{"entity-type":"item","numeric-id":1708394,"id":"Q1708394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"472ff308135b413ad6ae5f9b013c2ee1f92109d3","datavalue":{"value":{"amount":"+0.79709494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$7C98CABE-00CE-4C52-8311-3A2FC1A87491","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea5d874b6f98e926638f04ac7f9b9709c76d42ff","datavalue":{"value":{"entity-type":"item","numeric-id":396838,"id":"Q396838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f32c5a5e304e007a5a3dfae33b3e1c7b2af08167","datavalue":{"value":{"amount":"+0.796321","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$86746648-C587-45F2-B1AA-616AD69D20DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed4e264e3d086bedc4412d0e282aafeb8172f3e0","datavalue":{"value":{"entity-type":"item","numeric-id":402468,"id":"Q402468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb79b354ede21d08eb7b3e2855cab70f3a6d5d8c","datavalue":{"value":{"amount":"+0.793003","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2631073$F7F0B045-3C8C-4C77-805D-884B87EDF160","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2631073","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2631073"}}}}}