{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T18:47:25Z","timestamp":1760122045015,"version":"build-2065373602"},"reference-count":12,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2023,1,4]],"date-time":"2023-01-04T00:00:00Z","timestamp":1672790400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"groups GNSAGA of INdAM and Fondazione Cariverona","award":["Ricerca Scientifica di Eccellenza 2018","1268323N"],"award-info":[{"award-number":["Ricerca Scientifica di Eccellenza 2018","1268323N"]}]},{"DOI":"10.13039\/501100003130","name":"Research Foundation Flanders (FWO)","doi-asserted-by":"publisher","award":["Ricerca Scientifica di Eccellenza 2018","1268323N"],"award-info":[{"award-number":["Ricerca Scientifica di Eccellenza 2018","1268323N"]}],"id":[{"id":"10.13039\/501100003130","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>Given an edge-coloring of a graph G, we associate to every vertex v of G the set of colors appearing on the edges incident with v. The palette index of G is defined as the minimum number of such distinct sets, taken over all possible edge-colorings of G. A graph with a small palette index admits an edge-coloring which can be locally considered to be almost symmetric, since few different sets of colors appear around its vertices. Graphs with palette index 1 are r-regular graphs admitting an r-edge-coloring, while regular graphs with palette index 2 do not exist. Here, we characterize all graphs with palette index either 2 or 3 in terms of the existence of suitable decompositions in regular subgraphs. As a corollary, we obtain a complete characterization of regular graphs with palette index 3.<\/jats:p>","DOI":"10.3390\/sym15010154","type":"journal-article","created":{"date-parts":[[2023,1,5]],"date-time":"2023-01-05T01:33:30Z","timestamp":1672882410000},"page":"154","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Characterization of Graphs with Small Palette Index"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2597-7574","authenticated-orcid":false,"given":"Domenico","family":"Labbate","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica, Informatica ed Economia, Universit\u00e0 degli Studi della Basilicata, 85100 Potenza, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5876-0887","authenticated-orcid":false,"given":"Davide","family":"Mattiolo","sequence":"additional","affiliation":[{"name":"Department of Computer Science, KU Leuven Kulak, 8500 Kortrijk, Belgium"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7775-065X","authenticated-orcid":false,"given":"Giuseppe","family":"Mazzuoccolo","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Verona, 37134 Verona, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1166-3179","authenticated-orcid":false,"given":"Federico","family":"Romaniello","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, Informatica ed Economia, Universit\u00e0 degli Studi della Basilicata, 85100 Potenza, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gloria","family":"Tabarelli","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, Universit\u00e0 di Trento, 38122 Trento, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,1,4]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1007\/s00373-013-1298-8","article-title":"Minimum number of palettes in edge colourings","volume":"30","author":"Kalinowski","year":"2014","journal-title":"Graphs Comb."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.26493\/1855-3974.1528.d41","article-title":"A family of multigraphs with large palette index","volume":"17","author":"Avesani","year":"2019","journal-title":"ARS Math. Contemp."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1007\/s00373-015-1658-7","article-title":"Edge-colourings of 4-regular graphs with the minimum number of palettes","volume":"32","author":"Bonvicini","year":"2016","journal-title":"Graphs Comb."},{"key":"ref_4","first-page":"1","article-title":"Some results on the palette index of graphs","volume":"21","author":"Casselgren","year":"2019","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.46991\/PYSU:A\/2019.53.1.003","article-title":"On palette index of unicycle and bicycle graphs","volume":"53","author":"Ghazaryan","year":"2019","journal-title":"Proc. YSU A Phys. Math. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"85","DOI":"10.46991\/PYSU:A\/2022.56.3.085","article-title":"On the palette index of graphs having a spanning star","volume":"56","author":"Ghazaryan","year":"2022","journal-title":"Proc. YSU A Phys. Math. Sci."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"463","DOI":"10.7151\/dmgt.2015","article-title":"On the palette index of complete bipartite graphs","volume":"38","year":"2018","journal-title":"Discuss. Math. Graph Theory"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"36","DOI":"10.46991\/PYSU:A\/2021.55.1.036","article-title":"Two results on the palette index of a graphs","volume":"55","author":"Smbatyan","year":"2021","journal-title":"Proc. YSU A Phys. Math. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"112814","DOI":"10.1016\/j.disc.2022.112814","article-title":"Graphs with large palette index","volume":"345","author":"Mattiolo","year":"2022","journal-title":"Discrete Math."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., and Murty, U.S.R. (2008). Graph Theory, Springer.","DOI":"10.1007\/978-1-84628-970-5"},{"key":"ref_11","unstructured":"Jaeger, F. (1988). Nowhere-Zero Flow Problems, Academic Press."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1002\/jgt.22507","article-title":"Normal edge\u2013colourings of cubic graphs","volume":"94","author":"Mazzuoccolo","year":"2020","journal-title":"J. Graph Theory"}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/1\/154\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T17:59:21Z","timestamp":1760119161000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/15\/1\/154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,4]]},"references-count":12,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,1]]}},"alternative-id":["sym15010154"],"URL":"https:\/\/doi.org\/10.3390\/sym15010154","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2023,1,4]]}}}