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).

‹ 1 / ? › − 100% + Open in new tab Download Cite

Loading the full text…