{"entities":{"Q2113372":{"pageid":2124115,"ns":120,"title":"Item:Q2113372","lastrevid":57729396,"modified":"2026-04-01T03:33:58Z","type":"item","id":"Q2113372","labels":{"en":{"language":"en","value":"Graphs with large palette index"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7488440"}},"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":"Q2113372$11CFB381-D065-4845-BD57-C00714E853D9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d010a518323e35f376420e2ef7b45d931660acab","datavalue":{"value":{"text":"Graphs with large palette index","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2113372$91808CAF-A785-45F7-A5CF-E6AFBCA8BAFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"09e9fb89f84814ca360a45dbf8f588883afd66c3","datavalue":{"value":"1490.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113372$00389039-D873-48E8-91F0-0473283A5B30","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e39424d9d5ffc0a83bac1041d9b3d1cc73858943","datavalue":{"value":{"entity-type":"item","numeric-id":785825,"id":"Q785825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$595A0932-68DF-438A-AFE8-FE2BCB2749B7","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":"Q2113372$0E2FD88B-B6CA-4070-A7DB-7325329F633D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d6c399dc743e89f1c3cc7c2d5fa03fc1a7334073","datavalue":{"value":{"entity-type":"item","numeric-id":2113371,"id":"Q2113371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$5169C4A1-1555-47C1-B16D-B987A0D8A79D","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":"Q2113372$16AE8831-B6A5-458B-BBE0-BB1218DECAED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b9356dd598909cd854098580edef30353b10f02","datavalue":{"value":{"time":"+2022-03-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2113372$5AE26C7A-9AB1-4FE5-A3B6-391F3CF76998","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"299f95a8f483560917cbed2514a6f8632877a46a","datavalue":{"value":"https://arxiv.org/abs/2107.03827","type":"string"},"datatype":"url"},"type":"statement","id":"Q2113372$601290C0-FC5E-4B9B-8401-E2D861A80B32","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a7f6ec7ed4536a692be148ab278c31e53ddb740f","datavalue":{"value":"Let \\(G=(V, E)\\) be a simple connected graph. An edge-coloring of \\(G\\) is a map that assigns colors to the edges of \\(G\\) such that two incident edges obtain different colors. The minimum number of colors required in an edge-coloring of a graph \\(G\\) is called the chromatic index of \\(G\\).  The palette of a vertex \\(u \\in V(G)\\) with respect to the edge-coloring of \\(G\\) is the set of colors assigned to the edges incident to \\(u\\). Introduced in [\\textit{M. Hor\u0148\u00e1k} et al., Graphs Comb. 30, No. 3, 619--626 (2014; Zbl 1291.05066)] the palette index of a graph \\(G\\) is the minimum number of distinct palettes occurring in an edge-coloring of \\(G\\).  Note that the chromatic index of an \\(r\\)-regular graph equals either \\(r\\) or \\(r+1\\). Obviously, the chromatic index of an \\(r\\)-regular graph is \\(r\\) if and only if its palette index is one. The paper considers the question about the existence of an \\(r\\)-regular graph with the (maximum possible) palette index \\(r+1\\). In order to (partially) answer this question, the authors provide the result that shows that a graph \\(G\\) which does not admit a spanning subgraph with all vertices of even degree and without isolated vertices admits the palette index that exceeds the minimum vertex degree of \\(G\\). For an odd \\(r\\), this result allows a construction of a family of \\(r\\)-regular graphs having palette index equal to \\(r + 1\\).  The paper concludes with a description of a family of graphs whose palette index grows quadratically with respect to their maximum degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113372$1F74E44B-F8DA-432C-8811-28C5E2A57236","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"091ba179324c515c5e5d748b86d31c9f0c1910f8","datavalue":{"value":{"entity-type":"item","numeric-id":233536,"id":"Q233536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$08711F8F-B81D-4F70-8A52-65CE2F46815D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113372$B3700F51-1D56-4AE0-B0D7-14439ACF679A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c05090245d0027f2e86ba22ab531a1285d73b880","datavalue":{"value":"7488440","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113372$F18074C2-A250-49F3-ADFD-96762DEEE798","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5460c444abb9d7604f90c4e16cd9cc2ad2a35457","datavalue":{"value":"edge-coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113372$8BB496B6-3B25-43C4-9485-C7981F6EA947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76b2b78428d8f4f88266d559678169d726e29643","datavalue":{"value":"palette index","type":"string"},"datatype":"string"},"type":"statement","id":"Q2113372$CD94BB7F-FC2D-4499-A822-6233F2E713C4","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":"Q2113372$4610BC2D-3D8E-484C-A222-0ACCDEF29D17","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c77a0dadb72d9f1a14f3b2b6b6fd91c1ed092576","datavalue":{"value":"W3178034339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113372$48FAA71C-5E5B-4089-92EC-EB3289EEBAAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"231951b0ac417f68d1ef0a633a5e1dbe14790ad9","datavalue":{"value":{"entity-type":"item","numeric-id":5217064,"id":"Q5217064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$B8BF03DD-FA5D-49B5-A4E1-50D995C0640A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8bafe20abc774b9bb43ef901fe70aace07738c6a","datavalue":{"value":{"entity-type":"item","numeric-id":5354847,"id":"Q5354847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$186FE1EC-996B-439A-81FB-12C0C824701F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8da73a5c76dbe244bb1d30dff0952bf261ed905","datavalue":{"value":{"entity-type":"item","numeric-id":2306579,"id":"Q2306579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$3ECFA04B-4980-4BED-9DF2-6A1CD4077AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a383d7e8b46e8e3b922cc0bf86e5e3d0b73c2479","datavalue":{"value":{"entity-type":"item","numeric-id":2631073,"id":"Q2631073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$D3C515C1-2A75-4CF7-BFB8-50DC9A84E897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07f4c13eae732a653dcba41346fe3812123e6e1e","datavalue":{"value":{"entity-type":"item","numeric-id":5377233,"id":"Q5377233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$67FC6E55-F191-4DAF-9C2E-AC62046C704B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2904e92aa2ca91f3ed28f09761e1f7e2a1dbf15","datavalue":{"value":{"entity-type":"item","numeric-id":5239936,"id":"Q5239936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$2DA37D72-716F-4E52-B931-CB8F38D7988B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e0ca754e21e77aa680ebf84984d82814c2b2cae","datavalue":{"value":{"entity-type":"item","numeric-id":1708394,"id":"Q1708394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$F6490F51-F851-4BEF-980D-540F4E07A151","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":"Q2113372$B13615F8-2C55-4175-8E9D-CF701EE24E5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"86ea86d54a33a1b9ada1b9129ecaab386c9d3d43","datavalue":{"value":{"entity-type":"item","numeric-id":5100173,"id":"Q5100173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2113372$7D2201ED-CEDA-4D72-B786-E4C9E41EA95F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0760b6c9ffefaaf255336635acaec4f092d1dc5","datavalue":{"value":"10.1016/J.DISC.2022.112814","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2113372$78A8CEF3-0975-45D3-8BBD-B809A1476139","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f861003515615c764bf8b4ee1c8bcd7f0667ba45","datavalue":{"value":{"entity-type":"item","numeric-id":2631073,"id":"Q2631073"},"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":"Q2113372$4754CD38-35B0-43E9-9C6B-E7C84159975A","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":"c2391887cb40de8095e6b13693948db1f2ae8d8e","datavalue":{"value":{"amount":"+0.85095215","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":"Q2113372$DCF382AF-C866-4487-A0C6-E81701431D2E","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":"cb0c26218cb0f2863e2e39734bacd91d38110eaa","datavalue":{"value":{"amount":"+0.8360919","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":"Q2113372$29A28547-34BF-40CC-87BC-C6409B84DF1E","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":"b3ecf386e86adc3b6a0dc85e5bbcd8f90c48976b","datavalue":{"value":{"amount":"+0.7993213","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":"Q2113372$1FA66C79-4A1C-4825-ACA1-9253D6D614A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4087347b52e61950ae4a410de9f4e36943878389","datavalue":{"value":{"entity-type":"item","numeric-id":1042999,"id":"Q1042999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f05b19ee95b162ed020e9ee26c02ca6b4d654fa","datavalue":{"value":{"amount":"+0.7904594","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":"Q2113372$CBB55F73-69DF-4806-8849-36BDED69DF13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7593fc8421989335b9d42aa6a93160ed2d399b9e","datavalue":{"value":{"entity-type":"item","numeric-id":3470480,"id":"Q3470480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c939c0dbcca8fdf008ee2a8b6cc2bc23d0d4cd13","datavalue":{"value":{"amount":"+0.7879294","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":"Q2113372$CE6520EB-18FC-4EAF-B91E-A5FB3BF4676B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7e6f0c2b479f62c97e948b16bc04a4459b1e775","datavalue":{"value":{"entity-type":"item","numeric-id":2570116,"id":"Q2570116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7aed523c4fa574ea7d00fd03835d96e3496ac10c","datavalue":{"value":{"amount":"+0.78726494","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":"Q2113372$06B72EAF-E1A8-48C4-A1FC-C246C920A646","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":"2ad8d3e9b59c3075cc2ff029fc76a422ba1d63ce","datavalue":{"value":{"amount":"+0.7839751","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":"Q2113372$CAF7FD98-F156-4820-857A-5E1A35D9D177","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11f4e10bf4bf70789513eb2c40513dc33574e4f5","datavalue":{"value":{"entity-type":"item","numeric-id":790826,"id":"Q790826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"800180b9d658c24b3ab8f09f1d9988a758400e80","datavalue":{"value":{"amount":"+0.78392917","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":"Q2113372$54CDC01B-1DF5-47E3-B861-337804B04167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbb756f9b7273d3ed77aa941889d5fc2bb9880d1","datavalue":{"value":{"entity-type":"item","numeric-id":5190332,"id":"Q5190332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b39be290997cf6db9dedbbab9726dfeabfb54efe","datavalue":{"value":{"amount":"+0.77981335","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":"Q2113372$017D66F8-77C9-41CB-9248-5A29C9091241","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2113372","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2113372"}}}}}