|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Mathematics
Two results on the palette index of graphs
[Два результата об индексе палитры графов]
K. S. Smbatyan Yerevan State University, Faculty of Mathematics and Mechanics
Аннотация:
При правильной $\alpha$-реберной раскраске графа $G$ мы определяем палитру $S_G(v,\alpha)$ вершины $v\in V(G)$ как множество всех цветов, появляющихся на ребрах, смежных с $v$. Индекс палитры $\check{s}(G)$ графа $G$ является минимальным числом различных палитр, встречающихся при всех правильных реберных раскрасках $G$. Граф $G$ называется почти двудольным, если существует $ v\in V(G)$, так что $G-v$ является двудольным графом. В этой статье мы даем верхнюю границу индекса палитры почти двудольного графа $G$, используя разложение $G$ на циклы. Мы также даем оценку верхней границы для индекса палитры декартового произведения графов. В частности мы показываем, что для любых графов $G$ и $H$, $\check{s}(G\square H)\leq \check{s}(G)\check{s}(H)$.
Ключевые слова:
edge coloring, proper edge coloring, palette, palette index, Cartesian product.
Поступила в редакцию: 10.02.2021 Исправленный вариант: 28.02.2021 Принята в печать: 01.03.2021
Образец цитирования:
K. S. Smbatyan, “Two results on the palette index of graphs”, Уч. записки ЕГУ, сер. Физика и Математика, 55:1 (2021), 36–43
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzeru830 https://www.mathnet.ru/rus/uzeru/v55/i1/p36
|
Статистика просмотров: |
Страница аннотации: | 73 | PDF полного текста: | 36 | Список литературы: | 7 |
|