|
This article is cited in 1 scientific paper (total in 1 paper)
Mathematics
On the palette index of graphs having a spanning star
A. В. Ghazaryan, P. A. Petrosyan Yerevan State University, Faculty of Informatics and Applied Mathematics
Abstract:
A proper edge coloring of a graph $G$ is a mapping $\alpha:E(G)\longrightarrow \mathbb{N}$ such that $\alpha(e)\not=\alpha(e')$ for every pair of adjacent
edges $e$ and $e'$ in $G$. In a proper edge coloring of a graph $G$, the palette of a vertex $v \in V(G)$ is the set of colors assigned to the edges incident to $v$.
The palette index of $G$ is the minimum number of distinct palettes occurring in $G$ among all proper edge colorings of $G$. A graph $G$ has a spanning star, if it has a spanning subgraph which is a star. In this paper, we consider the palette index of graphs having a spanning star. In particular, we give sharp upper and lower bounds on the palette index of these graphs. We also provide some upper and lower bounds on the palette index of the complete split and threshold graphs.
Keywords:
edge coloring, palette index, spanning star, complete split graph, threshold graph.
Received: 22.03.2022 Revised: 14.09.2022 Accepted: 28.09.2022
Citation:
A. В. Ghazaryan, P. A. Petrosyan, “On the palette index of graphs having a spanning star”, Proceedings of the YSU, Physical and Mathematical Sciences, 56:3 (2022), 85–96
Linking options:
https://www.mathnet.ru/eng/uzeru979 https://www.mathnet.ru/eng/uzeru/v56/i3/p85
|
Statistics & downloads: |
Abstract page: | 68 | Full-text PDF : | 22 | References: | 14 |
|