О ациклическом b-хроматическом числе кубических графов

Основная информация

• ID статьи: 2511.01532
• Название: On acyclic b-chromatic number of cubic graphs
• Авторы: Marcin Anholcer (Познанский университет экономики и бизнеса), Sylwia Cichacz (Университет AGH), Iztok Peterin (Университет Марибора)
• Классификация: math.CO (комбинаторика), cs.DM (дискретная математика)
• Дата публикации: 4 ноября 2025 г.
• Ссылка на статью: https://arxiv.org/abs/2511.01532

Аннотация

В данной работе исследуются свойства ациклического b-хроматического числа (acyclic b-chromatic number) на кубических графах (cubic graphs). Ациклическая k-раскраска требует, чтобы соседние вершины имели разные цвета, и подграф, индуцированный любыми двумя цветами, был лесом. Ациклическое b-хроматическое число $A_b(G)$ — это максимальное количество цветов, используемых в ациклической раскраске, из которой невозможно выполнить ациклический шаг переокраски. Авторы доказывают, что за одним исключением все кубические графы имеют ациклическое b-хроматическое число 4 или 5, и детально исследуют это число для обобщённых графов Петерсена и (0,j)-призм.

Исследовательский контекст и мотивация

Исследуемая проблема

В работе изучается проблема ациклического b-хроматического числа графов, которая объединяет два классических концепции раскраски графов:

1. b-раскраска (b-coloring): введена Irving и Manlove в 1999 году; начинается с тривиальной раскраски и итеративно применяет шаги переокраски для максимизации количества используемых цветов
2. Ациклическая раскраска (acyclic coloring): предложена Grünbaum; требует, чтобы подграф, индуцированный любыми двумя цветами, был лесом (ациклическим)

Значимость

Данная проблема имеет следующую важность:

• Теоретическая ценность: связывает два важных варианта раскраски графов, формируя новый графовый инвариант
• Исследование регулярных графов: для d-регулярных графов центральным вопросом является, равно ли b-хроматическое число d+1. Кубические графы (3-регулярные графы) представляют простейший нетривиальный случай
• Комбинаторная оптимизация: предоставляет новую оптимизационную перспективу для задач раскраски графов

Ограничения существующих исследований

• Для b-хроматического числа φ(G) известно, что все кубические графы, кроме 4 исключений, имеют φ(G)=4 (Jakovac и Klavžar, 2010)
• Для ациклического b-хроматического числа $A_b(G)$ предыдущие работы 3 только установили базовую теоретическую основу, но не проводили систематического исследования конкретных классов графов
• Связь $A_b(G)$ с другими графовыми параметрами (такими как $\Delta(G)$, φ(G), A(G)) остаётся неясной

Исследовательская мотивация

Авторы ставят целью систематически исследовать ациклическое b-хроматическое число кубических графов, что является важным шагом к получению общих результатов для регулярных графов. Кубические графы как простейший нетривиальный класс регулярных графов могут предоставить ценные insights для более общих случаев.

Основные вклады

1. Установление базового диапазона для ациклического b-хроматического числа кубических графов: доказано, что для всех кубических графов G, кроме призмы $K_2\Box K_3$, выполняется $4 \leq A_b(G) \leq 5$
2. Выявление существенных различий с b-хроматическим числом: доказано существование бесконечного множества кубических графов G, удовлетворяющих $A_b(G)=4$, что контрастирует с конечностью результатов для b-хроматического числа
3. Полное определение ациклического b-хроматического числа для специальных классов графов:
   • Обобщённые графы Петерсена G(n,k): при $k \geq 3$ и достаточно большом n имеем $A_b(G(n,k))=5$
   • Призмы G(n,1): для $n \geq 4$ имеем $A_b(G(n,1))=4$; $A_b(K_2\Box K_3)=3$
   • (0,j)-призмы: при $j>0$ и $n \geq 5(j+2)$ имеем $A_b(\text{Pr}_n(0,j))=5$
4. Конструктивные методы доказательства: предоставлены явные конструкции 5-раскрасок, демонстрирующие два типа ациклических b-вершин (типы A и B)
5. Постановка открытых проблем: включая вычислительную сложность и ациклическое b-хроматическое число снарков

Подробное описание методов

Определение задачи

Ациклическая раскраска: k-раскраска $c: V(G) \to [k]$ графа G называется ациклической раскраской, если:

• соседние вершины имеют разные цвета (условие правильной раскраски)
• для любых $i,j \in [k]$ подграф $G[V_i \cup V_j]$, индуцированный цветами i и j, является лесом

Ациклический шаг переокраски: для класса цветов $V_i$, если каждая вершина $v \in V_i$ в своей замкнутой окрестности не имеет некоторого цвета $\ell_v$, и переокраска всех $v \in V_i$ в цвет $\ell_v$ сохраняет ациклическую раскраску, то это называется ациклическим шагом переокраски.

Ациклическое b-хроматическое число $A_b(G)$: начиная с тривиальной раскраски (каждая вершина имеет уникальный цвет), итеративно применяются ациклические шаги переокраски; максимальное количество цветов, когда дальнейшие шаги невозможны.

Ациклическая b-вершина: в раскраске, где невозможны ациклические шаги переокраски, вершина v называется ациклической b-вершиной, если любая её переокраска создаёт двухцветный цикл.

Теоретическая основа

Ключевые свойства:

1. Для кубических графов $A_b(G) \leq 5$ (следует из общей верхней границы $A_b(G) \leq \frac{1}{2}\Delta(G)^2 + 1$)
2. $A(G) \leq A_b(G)$ (ациклическое хроматическое число является нижней границей)
3. Классификация ациклических b-вершин:
   • Тип A: три соседа одного цвета
   • Тип B: соседи двух цветов

Блокирующий цикл (blocking cycle): для ациклической b-вершины v (цвет i), если цвет j отсутствует в её замкнутой окрестности, кратчайший двухцветный цикл, препятствующий переокраске v в цвет j, называется $j_v$-циклом.

Основные технические методы

1. Достижимость ациклической раскраски (Theorem 3.2)

Основная идея: любая 4-раскраска кубического графа может быть преобразована в ациклическую раскраску путём локальных корректировок, устраняющих все двухцветные циклы.

Алгоритмический процесс:

Вход: 4-раскраска c кубического графа G (возможно с двухцветными циклами)
Выход: ациклическая 4-раскраска графа G

while существует двухцветный цикл C do:
    Пусть C = v₁v₂...vₖv₁, цвета чередуются 1 и 2
    Пусть uᵢ — третий сосед вершины vᵢ
    
    Случай 1: существует uⱼ такой, что c(uⱼ) ∈ {1,2}
        В зависимости от цветов uⱼ₋₁ и uⱼ₊₁, переокрасить vⱼ в цвет 3 или 4
        
    Случай 2: все uᵢ имеют цвета не из {1,2}
        Предположим c(u₂)=3, переокрасить v₂ в 4
        Если создан новый двухцветный цикл, дополнительно скорректировать v₁,v₂,v₃

Ключевое свойство: каждая операция строго уменьшает количество двухцветных циклов, гарантируя завершение алгоритма.

2. Конструкция нижней границы для кубических графов (Theorem 3.3)

Стратегия: использовать основу доказательства Jakovac и Klavžar для b-хроматического числа, исправляя двухцветные циклы.

Этапы:

1. Начать раскраску на кратчайшем цикле C
2. Расширить на вершины около C, обеспечивая b-вершину для каждого цвета
3. Для четырёх конфигураций, где возникают двухцветные циклы (см. Figure 3 в 18), предоставить исправленные раскраски
4. Остальную часть раскрасить жадным методом, используя Theorem 3.2 для устранения двухцветных циклов

3. Доказательство точности верхней границы 5

Конструкция бесконечного множества кубических графов с $A_b(G)=4$ (Theorem 3.5):

Из кубического дерева T построить кубический граф C(T):

• Заменить каждую внутреннюю вершину v степени 3 треугольником abc
• В каждом листе T присоединить копию подграфа $H_3$

Ключевая лемма 3.4: вершина w степени 2 в $H_3$ не может быть ациклической b-вершиной в 5-раскраске.

Идея доказательства:

• w является точкой сочленения, её замкнутая окрестность содержит максимум 4 цвета
• если w — ациклическая b-вершина, она должна быть типа B (соседи одного цвета)
• но в $H_3$ два соседа w смежны, противоречие

Следовательно, C(T) не допускает 5-раскраски с ациклической b-раскраской, но 4-раскраска конструируется.

4. Конструкция 5-раскраски для обобщённых графов Петерсена (Theorem 4.1)

Условия: $k \geq 3$, $n \geq 5(2k + (-1)^k)$

Стратегия конструкции: спроектировать локальные конфигурации так, чтобы определённые вершины $x_j$ становились ациклическими b-вершинами типа B.

Случай нечётного k:

• Построить два цикла $C^1_j$ и $C^2_j$, содержащие $x_j$
• $C^1_j$: длина $k+2$, использует цвета $c^0_j, c^1_j, c^3_j$
• $C^2_j$: длина $2k+2$, использует цвета $c^0_j, c^2_j, c^3_j$
• Соседи $x_j$ окрашены в $c^3_j$ и $c^4_j$
• $C^1_j$ является $(c^1_j)_{x_j}$-циклом, $C^2_j$ является $(c^2_j)_{x_j}$-циклом

Повторяющийся паттерн: ациклическая b-вершина размещается через каждые $2k-1$ позиций; перестановки цветов обеспечивают согласованность.

Случай чётного k: аналогичная конструкция с интервалом $2k+1$.

Экспериментальная установка

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

Объекты исследования

• Общий класс кубических графов: все графы, где каждая вершина имеет степень 3
• Специальные классы графов:
  • Граф Петерсена P = G(5,2)
  • Призмы $K_2\Box K_3$, $K_{3,3}$, $G_1$
  • Обобщённые графы Петерсена G(n,k)
  • (0,j)-призмы $\text{Pr}_n(0,j)$
  • Графы C(T), построенные из кубических деревьев

Методы доказательства

• Конструктивные доказательства: явное предоставление схем раскраски
• Доказательство от противного: демонстрация несуществования определённых раскрасок
• Математическая индукция: алгоритм устранения двухцветных циклов
• Анализ конфигураций: перечисление возможных локальных структур

Результаты исследования

Основные результаты

Результат 1: Базовый диапазон для кубических графов (Theorem 3.3)

Теорема: Для каждого кубического графа G, кроме $K_2\Box K_3$, выполняется $A_b(G) \geq 4$. Кроме того, $A_b(K_2\Box K_3) = 3$.

Значение: в сочетании с верхней границей $A_b(G) \leq 5$ определены возможные значения ациклического b-хроматического числа кубических графов: {3,4,5}.

Результат 2: Контраст с b-хроматическим числом (Corollary 3.6)

Теорема: множество кубических графов, удовлетворяющих $A_b(G) < 5$, бесконечно.

Контраст: кубические графы с φ(G)<4 составляют только 4 графа (Theorem 3.1).

Конкретные примеры: для любого кубического дерева T имеем $A_b(C(T)) = 4$ (Theorem 3.5). Поскольку кубических деревьев бесконечно много, заключение верно.

Результат 3: Обобщённые графы Петерсена (Theorem 4.1, 4.2)

Ключевые находки:

• Граф Петерсена не может достичь 5 из-за ограничений существования ациклических b-вершин
• Обычные призмы (k=1) достигают максимум 4
• При параметрах k≥3 и достаточно большом n может быть достигнута верхняя граница 5

Результат 4: (0,j)-призмы (Theorem 5.1)

Теорема: Если $j > 0$ и $n \geq 5(j+2)$, то $A_b(\text{Pr}_n(0,j)) = 5$.

Ключевые моменты конструкции:

• Спроектировать локальную конфигурацию в вершинах $v^1_{2i+1}$
• Использовать два цикла $C^1_k$ и $C^2_k$ для блокирования определённых цветов
• Повторить конфигурацию через каждые $j+2$ позиций

Технические находки

Находка 1: Анализ типов ациклических b-вершин

Для не-b-вершин в кубических графах:

• Тип A (три соседа одного цвета): сложнее конструировать, требует специальных структур
• Тип B (соседи двух цветов): более распространён, реализуется через блокирование двухцветными циклами

Находка 2: Повторяемость локальных конфигураций

Посредством тщательного проектирования схемы перестановки цветов локальные конфигурации ациклической b-раскраски могут быть периодически повторены для конструирования произвольно больших графов.

Находка 3: Ограничивающая роль точек сочленения

Лемма 3.4 раскрывает: вершина степени 2, являющаяся точкой сочленения (как w в $H_3$), не может быть ациклической b-вершиной в 5-раскраске. Это является ключом к конструированию семейства графов с $A_b(G)=4$.

Анализ конкретных случаев

Случай 1: 4-раскраска графа Петерсена (Figure 2, левая часть)

• Использование цветов {1,2,3,4}
• Чёрные вершины — ациклические b-вершины
• Вершины цвета 1 — типа A (три соседа цвета 2)
• Вершины других цветов — типа B

Случай 2: Конструкция C(K_{1,3}) (Figure 4)

• Центральный треугольник окрашен в {1,2,3}
• Три копии $H_3$ окрашены в {1,2,3,4}
• Каждая копия $H_3$ содержит ациклическую b-вершину типа B
• Целое достигает $A_b=4$, но не может достичь 5

Связанные работы

Исследования b-раскраски

1. Irving & Manlove (1999): введение концепции b-хроматического числа, доказательство NP-трудности
2. Kratochvíl, Tuza, Voigt (2002): доказательство NP-трудности для связных двудольных графов
3. Jakovac & Klavžar (2010): доказательство того, что все кубические графы, кроме 4 исключений, имеют φ(G)=4
4. Гипотеза El Sahili & Kouider: d-регулярные графы (кроме графа Петерсена) с обхватом ≥5 имеют φ(G)=d+1

Исследования ациклической раскраски

1. Grünbaum (1973): введение ациклической раскраски, доказательство A(G)≤9 для плоских графов
2. Borodin (1979): доказательство A(G)≤5 для плоских графов
3. Alon, McDiarmid, Reed (1991): доказательство $A(G) \leq \lceil 50\Delta^{4/3}\rceil$
4. Gonçalves et al. (2020): улучшение до $A(G) \leq \frac{3}{2}\Delta^{4/3} + O(\Delta)$

Исследования ациклической b-раскраски

1. Anholcer, Cichacz, Peterin (2023): введение ациклического b-хроматического числа, установление базовой теории
   • Доказательство корректности определения (конечное завершение)
   • Общая верхняя граница $A_b(G) \leq \frac{1}{2}\Delta^2 + 1$
   • Доказательство того, что $A_b(G)$ может быть произвольно больше $\Delta(G)$, φ(G), A(G)

Позиция данной работы

Данная работа является первым систематическим исследованием ациклического b-хроматического числа для конкретного класса регулярных графов (кубических графов), заполняя пробел между теорией и конкретными классами графов.

Заключение и обсуждение

Основные выводы

1. Определение базового диапазона: за исключением $K_2\Box K_3$, все кубические графы G удовлетворяют $4 \leq A_b(G) \leq 5$
2. Существенные различия с b-хроматическим числом:
   • b-хроматическое число: только 4 кубических графа имеют φ(G)<4 (конечность)
   • Ациклическое b-хроматическое число: бесконечно много кубических графов с $A_b(G)=4$ (бесконечность)
3. Полная характеризация специальных классов графов:
   • Обобщённые графы Петерсена: при достаточно больших параметрах достигают верхней границы 5
   • Призмы: максимум достигают 4
   • Конструкции из кубических деревьев: ровно 4
4. Конструктивные методы: предоставлены систематические методы конструирования 5-раскрасок, основанные на периодическом повторении локальных конфигураций

Ограничения

1. Нерешённые проблемы:
   • Полная характеризация того, когда $A_b(G)=4$ и когда $A_b(G)=5$ для произвольных кубических графов остаётся неизвестной
   • Случаи обобщённых графов Петерсена G(n,k) при малых n или k=2 не полностью охвачены
2. Ограничения методов:
   • Конструктивные методы зависят от специальных структур графа (например, симметрии)
   • Отсутствует универсальный метод определения для нерегулярных или сложных кубических графов
3. Неизвестная вычислительная сложность: вычислительная сложность определения, имеет ли кубический граф $A_b(G)=4$ или $A_b(G)=5$, остаётся открытой проблемой

Направления будущих исследований

Статья предлагает три открытые проблемы:

Проблема 6.1 (Вычислительная сложность): какова вычислительная сложность определения, удовлетворяет ли кубический граф G условию $A_b(G)=4$ или $A_b(G)=5$?

Проблема 6.2 (Снарки): каково ациклическое b-хроматическое число снарков (кубических графов без 3-рёберной раскраски)?

Проблема 6.3 (Ациклические кубические графы): найти больше классов "ациклических кубических графов" (графов, где ациклическая степень каждой вершины также равна 3).

Гипотеза 6.4 (Связь обхвата и b-хроматического числа): если $g(G) > 2\phi(G)$, то $A_b(G) \geq \phi(G)$.

Предположение: при достаточно большом обхвате b-раскраска естественно является ациклической, поэтому ациклическое b-хроматическое число должно совпадать с b-хроматическим числом.

Глубокая оценка

Преимущества

1. Теоретическая полнота:
   • Систематическое построение базовой теоретической основы ациклического b-хроматического числа кубических графов
   • Строгие доказательства, ясная логика, каждая теорема имеет полное доказательство
   • Умелое использование существующих результатов по b-хроматическому числу (Jakovac & Klavžar)
2. Инновационность методов:
   • Проектирование локальных конфигураций: тщательно спроектированные механизмы блокирования двухцветными циклами для реализации ациклических b-вершин
   • Техника перестановки цветов: позволяет периодически повторять локальные конфигурации для конструирования произвольно больших графов
   • Классификационное обсуждение: классификация ациклических b-вершин на типы A и B упрощает анализ
3. Глубина результатов:
   • Выявление существенных различий: доказательство того, что $A_b(G)$ и φ(G) принципиально различаются на кубических графах (конечность vs бесконечность)
   • Конструктивные доказательства: не только доказывается существование, но и предоставляются явные конструкции
   • Полная характеризация специальных классов: точные значения для нескольких важных классов графов
4. Ясность изложения:
   • Многочисленные диаграммы (Figures 1-11) наглядно демонстрируют схемы раскраски
   • Постепенное введение концепций от простых к сложным
   • Чёткое разделение различных случаев (нечётные/чётные k, различные диапазоны параметров)

Недостатки

1. Охват результатов:
   • Для обобщённых графов Петерсена G(n,k) случаи k=2 или малых n не полностью решены
   • Отсутствует полная характеризация необходимых и достаточных условий для произвольных кубических графов
   • Не обсуждаются другие важные классы кубических графов (графы Кэли, клетки)
2. Алгоритмический аспект:
   • Не предоставлены алгоритмы определения или эвристические методы
   • Вычислительная сложность полностью открыта
   • Отсутствует обсуждение практических вычислений (хотя это теоретическая работа)
3. Зазор между границами:
   • Для многих кубических графов остаётся неизвестным, является ли $A_b(G)$ равным 4 или 5
   • Отсутствуют легко проверяемые достаточные условия
4. Связь с другими параметрами:
   • Кроме сравнения с φ(G), не глубоко исследуется связь с обхватом g(G), хроматическим числом χ(G), ациклическим хроматическим числом A(G)
   • Гипотеза 6.4 предложена, но не проверена

Влияние

1. Теоретический вклад:
   • Закладывает основу для исследования ациклического b-хроматического числа регулярных графов
   • Предоставленные конструктивные методы могут быть применимы к другим классам регулярных графов
   • Выявленное различие конечности vs бесконечности является важным теоретическим insight
2. Направления исследований:
   • Открывает новое направление исследований в теории раскраски кубических и регулярных графов
   • Предложенные открытые проблемы имеют чёткую исследовательскую ценность
   • Может стимулировать исследования специальных кубических графов, таких как снарки и клетки
3. Практическая ценность:
   • Как чисто теоретическое исследование, прямые приложения ограничены
   • Однако раскраска графов имеет приложения в планировании, распределении каналов, распределении регистров
   • Ациклическое ограничение имеет практический смысл в некоторых приложениях (избежание deadlock, циклических зависимостей)
4. Воспроизводимость:
   • Все доказательства полны и могут быть проверены
   • Методы конструирования явны, могут быть проверены вручную на малых графах
   • Подходит в качестве отправной точки для дальнейших исследований

Применимые сценарии

1. Теоретические исследования:
   • Исследователи теории раскраски графов
   • Исследования свойств регулярных графов
   • Задачи раскраски в комбинаторной оптимизации
2. Потенциальные приложения:
   • Проектирование сетей (избежание циклических зависимостей)
   • Задачи планирования (группировка задач с избежанием конфликтных циклов)
   • Оптимизация компилятора (распределение регистров)
3. Образовательная ценность:
   • Демонстрирует методы конструктивного доказательства
   • Хороший пример в комбинаторике и теории графов
   • Иллюстрирует переход от локального к глобальному конструированию

Библиография

Статья цитирует 24 справочных источника, ключевые из которых:

1. 17 Irving & Manlove (1999): оригинальная статья по b-хроматическому числу
2. 18 Jakovac & Klavžar (2010): ключевой результат по b-хроматическому числу кубических графов
3. 3 Anholcer, Cichacz, Peterin (2023): введение ациклического b-хроматического числа
4. 1 Alon, McDiarmid, Reed (1991): классическая верхняя граница для ациклической раскраски
5. 5 Borodin (1979): ациклическая раскраска плоских графов
6. 21 Kratochvíl, Tuza, Voigt (2002): сложность b-хроматического числа

Общая оценка: это высококачественная теоретическая математическая статья, систематически исследующая ациклическое b-хроматическое число кубических графов. Доказательства строги, результаты глубоки, особенно выявление существенных различий между ациклическим b-хроматическим числом и b-хроматическим числом на кубических графах. Хотя остаются многие открытые проблемы, данная работа закладывает прочную основу для дальнейших исследований в этой области. Рекомендуется для чтения исследователями в области теории графов и комбинаторной оптимизации.