DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2024): 0.8

5-year Journal Impact Factor (2024): 0.7

CiteScore (2024): 2.1

SNIP (2024): 1.162

Discussiones Mathematicae Graph Theory

Article in press

Authors:

A. Vesel

Aleksander Vesel

Faculty of Natural Sciences and Mathematics, University of Maribor

email: aleksander.vesel@um.si

0000-0003-3705-0071

Title:

The palette Index of some Cartesian products of graphs

PDF

Source:

Discussiones Mathematicae Graph Theory

Received: 2025-03-14 , Revised: 2025-06-10 , Accepted: 2025-06-10 , Available online: 2025-07-24 , https://doi.org/10.7151/dmgt.2594

Abstract:

The palette of a vertex \( v \) in a graph \( G \) is the set of colors assigned to the edges incident to \( v \). The palette index of \( G \) is the minimum number of distinct palettes among the vertices, taken over all proper edge colorings of \( G \). This paper presents results on the palette index of the Cartesian product \( G \Box H \), where one of the factor graphs is a path or a cycle. Additionally, it provides exact results and bounds on the palette index of the Cartesian product of two graphs, where one factor graph is isomorphic to a regular or class 1 nearly regular graph.

Keywords:

palette index, Cartesian product, regular graph

References:

  1. M. Avesani, A. Bonisoli and G. Mazzuoccolo, A family of multigraphs with large palette index, Ars Math. Contemp. 17 (2019) 115–124.
    https://doi.org/10.26493/1855-3974.1528.d41
  2. A. Bonisoli, S. Bonvicini and G. Mazzuoccolo, On the palette index of a graph: the case of trees, Lec. Notes of Semin. Interdiscip. Mat. 14 (2017) 49–55.
  3. S. Bonvicini and M.M. Ferrari, On the minimum number of bond-edge types and tile types: An approach by edge-colorings of graphs, Discrete Appl. Math. 277 (2020) 1–13.
    https://doi.org/10.1016/j.dam.2019.09.004
  4. S. Bonvicini and G. Mazzuoccolo, Edge-colorings of $4$-regular graphs with the minimum number of palettes, Graphs Combin. 32 (2016) 1293–1311.
    https://doi.org/10.1007/s00373-015-1658-7
  5. C.J. Casselgren and P.A. Petrosyan, Some results on the palette index of graphs, Discrete Math. Theor. Comput. Sci. 21(3) (2019) #11.
    https://doi.org/10.23638/DMTCS-21-3-11
  6. G. Chartrand, F. Harary and P. Zhang, On the geodetic number of a graph, Networks 39 (2002) 1–6.
    https://doi.org/10.1002/net.10007
  7. R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs (CRC Press, Boca Raton, 2011).
  8. M. Horň\'ak and J. Hud\'ak, On the palette index of complete bipartite graphs, Discuss. Math. Graph Theory 38 (2018) 463–476.
    https://doi.org/10.7151/dmgt.2015
  9. M. Horň\'ak, R. Kalinowski, M. Meszka and M. Woźniak, Minimum number of palettes in edge colorings, Graphs Combin. 30 (2014) 619–626.
    https://doi.org/10.1007/s00373-013-1298-8
  10. E.S. Mahmoodian, On edge-colorability of Cartesian products of graphs, Canad. Math. Bull. 24 (1981) 107–108.
    https://doi.org/10.4153/CMB-1981-017-9
  11. D. Mattiolo, G. Mazzuoccolo and G. Tabarelli, Graphs with large palette index, Discrete Math. 345 (2022) 112814.
    https://doi.org/10.1016/j.disc.2022.112814
  12. B. Mohar, On edge-colorability of products of graphs, Publ. Inst. Math. (Beograd) 36 (1984) 13–16.
  13. K.S. Smbatyan, Some results on palette index of Cartesian product graphs, Math. Probl. Comput. Sci. 55 (2021) 26–34.
    https://doi.org/10.51408/1963-0070
  14. K.S. Smbatyan, Two results on the palette index of graphs, Proc. YSU A: Phys. Math. Sci. 55 (2021) 36–43.
    https://doi.org/10.46991/PYSU:A/2021.55.1.036
Close