2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge
For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $φ_1,\cdots,φ_k$ such that $φ_i(v)\neφ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $χ^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $χ^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $χ^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $χ^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $χ^{\star}_{\ell}(G)=4$, which matches the known upper bound $χ^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $χ^{\star}_{\ell}$ for correspondence coloring, $χ^{\star}_c$. In fact, all bounds stated above for $χ^{\star}_{\ell}$ also hold for $χ^{\star}_c$.
academic

Упаковка списков и соответственная упаковка плоских графов

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

  • ID статьи: 2401.01332
  • Название: List Packing and Correspondence Packing of Planar Graphs
  • Авторы: Daniel W. Cranston (Virginia Commonwealth University), Evelyne Smith-Roberge (Georgia Tech)
  • Классификация: math.CO (комбинаторная математика)
  • Дата публикации: 6 декабря 2024 г. (версия 3 на arXiv)
  • Ссылка на статью: https://arxiv.org/abs/2401.01332

Аннотация

В данной работе исследуются задачи упаковки списков (list packing) и соответственной упаковки (correspondence packing) для плоских графов. Для графа GG и назначения списков LL, где ∣L(v)∣=k|L(v)|=k для всех вершин vv, LL-упаковка содержит LL-раскраски ϕ1,⋯ ,ϕk\phi_1,\cdots,\phi_k такие, что для всех vv и различных i,j∈{1,…,k}i,j\in\{1,\ldots,k\} выполняется ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v). Обозначим через χℓ⋆(G)\chi^{\star}_{\ell}(G) минимальное значение kk, при котором граф GG имеет LL-упаковку для каждого назначения списков LL с ∣L(v)∣=k|L(v)|=k. В статье доказано: (i) для всех плоских графов GG с обхватом не менее 3 выполняется χℓ⋆(G)≤8\chi^{\star}_{\ell}(G)\leq 8; (ii) для всех плоских графов GG с обхватом не менее 4 выполняется χℓ⋆(G)≤5\chi^{\star}_{\ell}(G)\leq 5; (iii) для всех плоских графов GG с обхватом не менее 5 выполняется χℓ⋆(G)≤4\chi^{\star}_{\ell}(G)\leq 4. Эти результаты также справедливы для аналогичного параметра χc⋆\chi^{\star}_c соответственной раскраски.

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

  1. Основная проблема: Исследование верхних границ для чисел упаковки списков и соответственной упаковки плоских графов. Упаковка списков является обобщением раскраски списков и требует нахождения нескольких непересекающихся раскрасок списков.
  2. Значимость проблемы:
    • Раскраска списков является классической задачей теории графов с широким теоретическим и прикладным значением
    • Задачи упаковки являются естественным обобщением задач раскраски и моделируют оптимизацию распределения ресурсов
    • Плоские графы как важный класс графов имеют особое теоретическое значение для изучения свойств раскраски
  3. Существующие ограничения:
    • Cambie и соавторы в 2024 году доказали, что χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 для всех плоских графов GG
    • Однако эта граница является относительно грубой и требует дальнейшего улучшения
    • Отсутствует детальный анализ плоских графов с различными обхватами
  4. Исследовательская мотивация:
    • Улучшение известных верхних границ, в частности проблемы, поставленной Cambie и соавторами
    • Установление точных связей между обхватом и числом упаковки
    • Разработка единого аналитического подхода для соответственной раскраски

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

  1. Значительное улучшение верхних границ для упаковки плоских графов: улучшение χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 до χc⋆(G)≤8\chi^{\star}_c(G)\leq 8
  2. Установление точных связей между обхватом и числом упаковки:
    • Обхват ≥ 4: χc⋆(G)≤5\chi^{\star}_c(G)\leq 5
    • Обхват ≥ 5: χc⋆(G)≤4\chi^{\star}_c(G)\leq 4 (оптимально)
  3. Предоставление полностью проверяемых вручную доказательств: в отличие от одновременных работ, избегаются компьютерные проверки
  4. Единообразная обработка упаковки списков и соответственной упаковки: все результаты справедливы для обоих типов упаковки
  5. Доказательство оптимальности границы для обхвата ≥ 5: через построение примеров, показывающих, что граница является точной

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

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

Упаковка списков: Дан граф GG и kk-назначение LL (каждой вершине vv назначено ∣L(v)∣=k|L(v)|=k доступных цветов). Требуется найти kk раскрасок списков ϕ1,…,ϕk\phi_1,\ldots,\phi_k такие, что:

  1. Каждая ϕi\phi_i является допустимой LL-раскраской
  2. Для любой вершины vv и различных i,ji,j выполняется ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v)

Соответственная упаковка: Аналогичное определение, но использующее соответственные раскраски вместо раскрасок списков с более строгими ограничениями.

Основная техническая схема

1. Метод вспомогательного двудольного графа

  • Определение: Для вершины vv и существующей упаковки ϕ\phi строится вспомогательный двудольный граф HvH_v
  • Доля A: представляет kk цветов
  • Доля B: представляет kk раскрасок ϕ1,…,ϕk\phi_1,\ldots,\phi_k
  • Рёбра: iϕj∈E(H)i\phi_j \in E(H) тогда и только тогда, когда возможно установить ϕj(v)=i\phi_j(v)=i

2. Применение теоремы Холла

Использование теоремы Холла для определения наличия совершенного паросочетания в двудольном графе:

  • Препятствие: множество X⊆AX \subseteq A такое, что ∣N(X)∣<∣X∣|N(X)| < |X|
  • Ключевое наблюдение: размер препятствий в (s,t)(s,t)-двудольном графе ограничен

3. Инструменты структурного анализа

Предложение 5: Если GG является (s,t)(s,t)-двудольным графом и существует X⊆AX \subseteq A такое, что ∣X∣>∣N(X)∣|X| > |N(X)|, то t+1≤∣X∣≤s−tt+1 \leq |X| \leq s-t.

Следствие 6: Если χc⋆(G−v)≤k\chi^{\star}_c(G-v) \leq k и d(v)≤k/2d(v) \leq k/2, то χc⋆(G)≤k\chi^{\star}_c(G) \leq k.

Основные стратегии доказательства

1. Случай обхвата ≥ 4 (теорема 12)

  • Метод разрядки: каждой вершине назначается начальный заряд, равный её степени
  • Правила разрядки: каждая вершина степени 3 получает заряд 1/31/3 от каждого соседа
  • Запрещённые конфигурации:
    • Вершины степени 3 не могут быть смежны
    • Не существует ребра vwvw такого, что d(v)=3d(v)=3 и d(w)≤4d(w) \leq 4
    • Вершины степени 5 смежны не более чем с тремя вершинами степени 3

2. Случай обхвата ≥ 5 (теорема 15)

Использование более тонкого анализа:

  • Ключевая лемма: каждая вершина (4,2)(4,2)-двудольного графа инцидентна по крайней мере двум рёбрам, содержащимся в 1-факторе
  • Анализ путей: особое внимание к путям степени 3 вершин xvyxvy
  • Техника переупаковки: модификация раскрасок соседних вершин для создания пространства расширения целевой вершины

3. Случай общих плоских графов (теорема 19)

  • Структурная теорема Бородина: плоский граф с δ(G)≥5\delta(G) \geq 5 содержит треугольник uvwuvw такой, что d(u)+d(v)+d(w)≤17d(u)+d(v)+d(w) \leq 17
  • Анализ типов препятствий: определение 4 типов препятствий и их отдельная обработка
  • Сложная переупаковка: возможна одновременная модификация раскрасок двух вершин

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

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

Основные технические инновации

1. Систематическая классификация препятствий

Определены 4 типа препятствий в (8,3)(8,3)-двудольных графах:

  • Тип 1: ∣X∣=5|X|=5, ∣N(X)∣=3|N(X)|=3
  • Тип 2: ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3 с определённой структурой расширения
  • Тип 3: аналогичен типу 2, но с другой структурой расширения
  • Тип 4: ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3, не принадлежащие первым трём типам

2. Единый аналитический подход

Через лемму 8 установлена эквивалентность между раскрасками списков и соответственными раскрасками, позволяющая "выпрямлять" расположения на древовидных структурах.

3. Точные ограничения на степени

Использование формулы Эйлера для установления связи между обхватом и средней степенью:

  • Средняя степень плоского графа с обхватом gg меньше 2g/(g−2)2g/(g-2)
  • Обхват 4: средняя степень <4< 4
  • Обхват 5: средняя степень <10/3< 10/3

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

Формулировка теорем

  1. Теорема 1: χc⋆(G)≤8\chi^{\star}_c(G) \leq 8 для всех плоских графов GG
  2. Теорема 2: χc⋆(G)≤5\chi^{\star}_c(G) \leq 5 для всех плоских графов GG с обхватом ≥ 4
  3. Теорема 3: χc⋆(G)≤4\chi^{\star}_c(G) \leq 4 для всех плоских графов GG с обхватом ≥ 5, и эта граница оптимальна

Оптимальность

Доказана через примеры циклов CkC_k (k≥3k \geq 3):

  • χℓ⋆(Ck)=3<4=χc⋆(Ck)\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)
  • Показывает, что соответственная упаковка более сложна, чем упаковка списков
  • Граница 4 для обхвата ≥ 5 является точной

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

  1. Cambie и соавторы (2024): первое систематическое исследование задач упаковки, доказано χc⋆(G)≤10\chi^{\star}_c(G) \leq 10
  2. Одновременные работы: независимая работа Cambie, Cames van Batenburg, Zhu, доказывающая аналогичные результаты с использованием компьютерной проверки
  3. Классическая теория раскраски: основана на классических работах Heawood, Ringel-Youngs и других по раскраске графов на поверхностях
  4. Соответственная раскраска: теоретический подход, разработанный Dvořák-Postle и соавторами

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

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

  1. Значительное улучшение верхних границ для чисел упаковки плоских графов
  2. Установление точных связей между обхватом и числом упаковки
  3. Разработка полностью конструктивного метода доказательства
  4. Единообразная обработка упаковки списков и соответственной упаковки

Ограничения

  1. Доказательства носят технический характер с обширным анализом случаев
  2. Задача для графов на общих поверхностях остаётся нерешённой
  3. Оптимальность некоторых границ полностью не установлена

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

В статье предложено 6 открытых проблем:

  1. Определение точных значений χℓ⋆(P3)\chi^{\star}_\ell(\mathcal{P}_3) и χℓ⋆(P4)\chi^{\star}_\ell(\mathcal{P}_4)
  2. Исследование чисел упаковки для графов с ограниченной максимальной средней степенью
  3. Задачи упаковки для плоских двудольных графов
  4. Числа упаковки для графов на общих поверхностях
  5. Связь с числом Heawood
  6. Числа упаковки для графов без полных подграфов

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

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

  1. Значительный теоретический вклад: существенное улучшение границ для важной задачи
  2. Методологические инновации: классификация препятствий и единый аналитический подход имеют универсальное значение
  3. Полнота доказательств: избегаются компьютерные проверки, все доказательства поддаются ручной верификации
  4. Оптимальность результатов: случай обхвата ≥ 5 достигает оптимальной границы
  5. Ясность изложения: хорошо организованные технические детали и поясняющие примеры

Недостатки

  1. Сложность доказательств: обширные технические детали и анализ множества случаев
  2. Ограниченная применимость методов: неясна применимость методов к другим классам графов
  3. Отсутствие анализа сложности: не рассматривается вычислительная сложность алгоритмов

Влияние

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

Области применения

  1. Избежание конфликтов при распределении ресурсов
  2. Распределение спектра и раскраска сетей
  3. Задачи планирования с ограничениями удовлетворения
  4. Задачи упаковки в комбинаторной оптимизации

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

В статье цитируются 20 важных работ, включая:

  • Классические результаты Бородина о структуре плоских графов
  • Основополагающие работы Cambie и соавторов о задачах упаковки
  • Теорию соответственной раскраски Dvořák-Postle
  • Классическую теорию раскраски графов на поверхностях Heawood

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