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

dmtcs:4509 - Discrete Mathematics & Theoretical Computer Science, May 11, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-11
Some results on the palette index of graphsArticle

Authors: C. J. Casselgren ; Petros A. Petrosyan

    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.


    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: May 11, 2019
    Accepted on: March 4, 2019
    Submitted on: May 16, 2018
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 678 times.
    This article's PDF has been downloaded 218 times.