Natural Sciences, Mathematics, 2026
TWO RESULTS ON THE PALETTE INDEX OF GRAPHS
This is an open access article distributed under the
Creative Commons Attribution License, which permits unrestricted use, distribution,
and reproduction in any medium, provided the original work is properly cited.
Submitted: 2025-01-27
© 2026 by author(s) and The Gufo Inc.
This work is licensed under Creative Commons Attribution–NonCommercial International License
(CC BY-NC 4.0).
Abstract
Given a proper edge coloringαof a graphG, we define the paletteSG(v,α)of a vertexv∈V(G)as the set of all colors appearing on edges incident withv. The palette indexˇs(G)ofGis the minimum number of distinct palettesoccurring in a proper edge coloring ofG. A graphGis called nearly bipartite ifthere existsv∈V(G)so thatG−vis a bipartite graph. In this paper, we givean upper bound on the palette index of a nearly bipartite graphGby using thedecomposition ofGinto cycles. We also provide an upper bound on the paletteindex of Cartesian products of graphs. In particular, we show that for any graphsGandH, ˇs(GH)≤ˇs(G)ˇs(H).