Аннотация:
При правильной $\phi$-реберной раскраске графа $G$ мы определяем палитру $S_G(v,\phi)$ вершины $v \in V(G)$ как множество всех цветов, появляющихся на ребрах, смежных с $v$. Индекс палитры $cyc(G)$ графа $G$ является минимальным числом различных палитр, встречающихся при всех правильных реберных раскрасках $G$. В этой статье мы даем верхнюю границу индекса палитры графа $G$ в терминах цикломатического числа $cyc(G)$ и максимальной степени $\Delta(G)$ графа $G$. Мы также даем верхнюю точную оценку для индекса палитры одноцикловых и двуцикловых графов.
Полный текст:
PDF файл (377 kB)