Эта публикация цитируется в 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.

MSC: 05C15; 05C76

Поступила в редакцию: 10.02.2021
Исправленный вариант: 28.02.2021
Принята в печать: 01.03.2021

Язык публикации: английский

DOI: 10.46991/PYSU:A/2021.55.1.036