Casselgren, C. J. and Petrosyan, Petros A. - Some results on the palette index of graphs

dmtcs:4509 - Discrete Mathematics & Theoretical Computer Science, May 11, 2019, Vol. 21 no. 3
Some results on the palette index of graphs

Authors: Casselgren, C. J. and Petrosyan, Petros A.

Given a proper edge coloring $\varphi$ of a graph $G$, we define the palette $S_{G}(v,\varphi)$ of a vertex $v \in V(G)$ as the set of all colors appearing on edges incident with $v$. The palette index $\check s(G)$ of $G$ is the minimum number of distinct palettes occurring in a proper edge coloring of $G$. In this paper we give various upper and lower bounds on the palette index of $G$ in terms of the vertex degrees of $G$, particularly for the case when $G$ is a bipartite graph with small vertex degrees. Some of our results concern $(a,b)$-biregular graphs; that is, bipartite graphs where all vertices in one part have degree $a$ and all vertices in the other part have degree $b$. We conjecture that if $G$ is $(a,b)$-biregular, then $\check{s}(G)\leq 1+\max\{a,b\}$, and we prove that this conjecture holds for several families of $(a,b)$-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.


Source : oai:arXiv.org:1805.00260
Volume: Vol. 21 no. 3
Section: Graph Theory
Published on: May 11, 2019
Submitted on: May 16, 2018
Keywords: Mathematics - Combinatorics


Share