Некоторые результаты об индексе палитры графиков

ВВЕДЕНИЕ

В статье рассматриваются неориентированные, конечные, связные графы без кратных  рёбер и петель. Множество вершин графа G мы обозначим через V(G), а множество рёбер - через E(G). Степень вершины V графа G  обозначим через d(v), а максимальную степень - через Δ(G). Все термины и понятия, которые явно не упомянуты, вы можете найти в [1].

В дискретной математике задачи о раскраске являются одной из самых популярных и актуальных тем. Важность этих задач обусловлена наличием тесной связи со многими прикладными задачами. В частности, существует значительная взаимосвязь между задачами теории расписаний и раскраски графов. Например, задача по составлению оптимального расписания для экзаменационного периода приводит к вычислению хроматического числа графа. К задаче по вычислению хроматического класса графа приводится задача по составлению расписания спортивных соревнований, а задачи рёберной раскраски особого типа двусторонних графов для многих работ послужили моделями существования,  построения и оценки числовых параметров учебных расписаний.  

Вероятно, самыми известными и применяемыми хроматическими параметрами при вершинной и рёберной раскраске графа являются параметры, соответственно, хроматический индекс и хроматическое число. Однако, есть много других хроматических параметров. Например, циклический хроматический индекс [2], список хроматических чисел [3] и т. д. Хроматические параметры могут предоставить дополнительные и полезные данные о структуре графа. Например, хроматический индекс однородного графа дает информацию о существовании совершенной комбинации в графе.

В данной статье мы изучаем  хроматический параметр графа G, который называется индекс палитры.  Этот параметр представлен в статье [4] и обозначается через . Данный параметр можно представить следующим образом. Допустим  - правильная рёберная раскраска графа G, а  - вершина графа G. Множество цветов рёбер, смежных вершине , называется  палитрой вершины v- (в соответствии с раскраской  ) и обозначается через  .

Для всех правильных рёберных раскрасок графа G можем рассмотреть  множество  палитр всех вершин. Максимальная мощность множества -это . Индекс палитры G является минимальным числом различных палитр во всем G по всем рёберным раскраскам и обозначается через  по всем  правильным ребёрным раскраскам графа G/.

Как показано в статье [4], индекс палитры регулярного графа равен 1 только в том случае, если он из первого класса (в [5] вы можете найти определения первого и второго классов). Более того, он отличается от 2. Как упоминается в статье  [6], индекс палитры d-регулярного графа второго класса удовлетворяет неравенству . Следовательно, s ̌(G)= 3, если G 2-регулярный граф второго класса.

Поскольку определение хроматического числа графа G является NP-полной задачей [7],  определение индекса палитры тоже является NP-полной задачей даже для кубических графов [4]. Фактически, это означает, что индекс палитры равен 1 или нет является NP- полной задачей.

Используя теорему реберной раскраски Визинга, мы можем сверху оценить индекс палитры графа G, имеющего максимальную степень Δ: . Несложно построить графы, индексы палитры которых будут значительно меньше  2^(Δ+1)-2. Действительно, в статье [8] описано бесконечное семейство мультиграфов, индексы палитр  которых Δ² асимптотически растут. Но остается под вопросом, есть ли такой пример кратных рёбер? В статье [8] предлагается доказать, что существует p(Δ) многочлен, так что для любого графа G с Δ максимальной степенью имеет место следующее неравенство:

s ̌(G) ≤p (Δ).

Существует мало результатов об индексах палитры нерегулярных графов. В статье [9] полностью изучен индекс палитры полного двустороннего графа  K_a,b, когда a <5.

В статье [10] изучен индекс палитры двусторонних графов. В частности, получено значение индекса палитры сети.

В статье [11] изучен индекс палитры дерева T и была доказана оценка . Более того, были построены  деревья и было показано, что эта оценка доступна для  деревьев.

В этой статье мы концентрируемся на индексе палитры нерегулярных графов. В частности, мы даем верхнюю точную оценку для индекса палитры одноцикловых графов. Даем  верхнюю точную оценку для индекса палитры двуцикловых графов. Более того, мы даем верхнюю оценку для индекса палитры в зависимости от максимальной степени и цикломатического числа графа.

Определения

Давайте вспомним алгоритм раскраски дерева, приведенный в статье [11]. Как показано в статье [11], мы можем раскрасить дерево T с Δ максимальной степенью, использую  следующие палитры:

, где    и   , а также все цвета взяты по Δ модулю. Мы раскрасим дерево T следующим образом:

Выбираем любую из вершин T, например v, и обозначаем в качестве корня. Смежные к  рёбра произвольным образом красим цветами палитры . Начинаем обходить поперек Т. Каждый раз, когда мы посещаем новую вершину, окрашивается только одно смежное ребро. Мы возьмем палитру, мощность которой равна степени вершины, которая также содержит цвет уже окрашенного ребра и раскрасим рёбра. Очевидно, что таким образом мы сможем раскрасить все дерево T.

Отметим, что из каждого ребра нам нужна палитра с 1, ..., Δ. Но это не всегда возможно.

Определение 1.  Для данных  Δ натуральных чисел множество палитр  назовем множеством оригинальных палитр, где , и  и все цвета взяты по Δ модулю.

Определение 2.  Для данных  Δ натуральных чисел множество палитр  назовем множеством стандартных палитр, где ,, если для каждого   и может быть индекс , для которого , где  .

Определение 3. Если для данного Δ натурального числа мы уже определили множество стандартных палитр, то любую палитру,  не похожую на стандартную, назовем лишней палитрой.

Индекс палитры одноцикловых графов

Одноцикловый граф- это связный, простой граф, который имеет только один цикл.

Определение 4. (* условие) Мы можем сказать, что граф G с одним  циклом  удовлетворяет условию, если:

·  цикл имеет нечетную длину

·  цикл имеет какую-либо вершину, степень которой больше 2-х

· В цикле   не существуют две соседние вершины, степени которых больше 2-х

· Максимальная степень графа G четное число.

Теорема 1. Следующее неравенство верно для одноциклового графа G

Более того, данная оценка доступна.

Доказательство. Пусть  является циклом одноциклового графа G , а Δ - максимальная степень G. В качестве начального множества палитр возьмем множество оригинальных палитр для Δ.

Легко заметить, что неравенство имеет место, когда G является циклом. Действительно, мы можем раскрасить цикл  четной длины  множеством палитр   и цикл нечётной длины- множеством палитр . Так как , и мы можем раскрасить цикл максимум 3-мя разными палитрами, то неравенство верно.

Теперь рассмотрим случай, когда цикл  имеет вершину, степень которой больше 2-х. Сначала раскрасим цикл , а затем остальные части графа G .

Пусть степень вершины  больше 2-х и рёбра ,  исходят из  .  Связная часть графа  , которая содержит вершину , назовём поддеревом  графа G и обозначим через .

Случай 1. Цикл  имеет четную длину. Раскрасим  цветами 0 и 1. Для каждой вершины  мы имеем два смежных ребра, раскрашенные цветами 0 и 1. Множество оригинальных палитр содержит палитры мощностью , содержащая цвета 0 и 1. То есть, мы можем раскрасить все  поддеревья палитрами множества оригинальных палитр. Следовательно, для того, чтобы раскрасить граф G, мы используем максимум  штук палитр.

Случай 2. Цикл  имеет нечётную длину. Предположим, что на цикле  не существуют две соседние вершины, степень которых больше 2-х. Пусть вершина  принадлежит ,  и допустим, что  и   соседние вершины со степенью 2. Мы раскрасим  1, а -2.   Путь нечётной длины   мы раскрасим последовательно цветами 0 и 1, начиная с вершины . Поддерево    мы можем раскрасить как дерево, так как мы можем раскрасить нераскрашенные  рёбра, смежные , цветами .

Если Δ нечётная, то мы заменяем палитру  множества оригинальных палитр палитрой .

Для любой  вершины, степень которой больше 2-х , мы имеем поддерево   и можем раскрасить его как дерево. Несложно заметить, что когда Δ чётная,  мы используем 1 лишнюю  палитру.

Если существуют две соседние вершины , степень которых больше 2-х, то  мы раскрасим 2, а чётный путь  последовательно цветами 0 и 1, начиная с вершины .  можно раскрасить как дерево, так как мы можем раскрасить нераскрашенные  рёбра, смежные , цветами .  можно раскрасить как дерево, так как мы можем раскрасить нераскрашенные  рёбра, смежные  , цветами . Затем раскрашиваем все остальные поддеревья как дерево. Следовательно, мы используем максимум  палитр.

Давайте теперь докажем, что равенство имеет место. Мы используем дерево , указанное в статье [11]. Возьмем цикл  нечётной длины и какую-либу вершину из  соединим с каким-либо листком . Предположим, что равенство не имеет место  и раскрасим  вышеуказанным способом.  не возможно раскрасить палитрой меньше 3-х.

Если мы отдалим вершины ,  получим раскраску , которое использует меньше палитры, что является противоречием. Доказано.