Two results on the palette index of graphs

При правильной $\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)$.