|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
Two results on the palette index of graphs
K. S. Smbatyan Yerevan State University, Faculty of Mathematics and Mechanics
Abstract:
Given a proper edge coloring $\alpha$ of a graph $G$, we define the palette $S_G(v,\alpha)$ 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$. A graph $G$ is called nearly bipartite if there exists $ v\in V(G)$ so that $G-v$ is a bipartite graph. In this paper, we give an upper bound on the palette index of a nearly bipartite graph $G$ by using the decomposition of $G$ into cycles. We also provide an upper bound on the palette index of Cartesian products of graphs. In particular, we show that for any graphs $G$ and $H$, $\check{s}(G\square H)\leq \check{s}(G)\check{s}(H)$.
Keywords:
edge coloring, proper edge coloring, palette, palette index, Cartesian product.
Received: 10.02.2021 Revised: 28.02.2021 Accepted: 01.03.2021
Citation:
K. S. Smbatyan, “Two results on the palette index of graphs”, Proceedings of the YSU, Physical and Mathematical Sciences, 55:1 (2021), 36–43
Linking options:
https://www.mathnet.ru/eng/uzeru830 https://www.mathnet.ru/eng/uzeru/v55/i1/p36
|
Statistics & downloads: |
Abstract page: | 73 | Full-text PDF : | 36 | References: | 7 |
|