Эта публикация цитируется в
1 статье
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
Аннотация:
Правильной реберной раскраской графа
$G$ называется такое отображение
$\alpha: E(G)\longrightarrow \mathbb{N},$ при котором
$\alpha(e) \neq \alpha(e^{\prime})$ для любой пары смежных ребер
$e$ и
$e^{\prime}$ графа
$G.$ Для правильной реберной раскраски графа
$G$ определим палитру вершины
$v\in V(G)$ как множество всех цветов, присвоенных ребрам, инцидентным вершине
$v$. Палитровым индексом графа
$G$ называется минимальное количество различных палитр, встречаю- щихся в правильных реберных раскрасках графа
$G$. Говорят, что граф
$G$ имеет остовную звезду, если у него есть остовный подграф, который является звездой. В настоящей статье нами рассмотрен палитровый индекс графов, имеющих остовную звезду. В частности в этой работе даны достижимые верхние и нижние оценки палитрового индекса графов. Нами также получены некоторые верхние и нижние границы палитрового индекса полных расщепляемых графов и пороговых графов.
Ключевые слова:
edge coloring, palette index, spanning star, complete split graph, threshold graph.
MSC: 05C15 Поступила в редакцию: 22.03.2022
Исправленный вариант: 14.09.2022
Принята в печать: 28.09.2022
Язык публикации: английский
DOI:
10.46991/PYSU:A/2022.56.3.085