Граф является выбираемым (также известным как -list-colourable ), если для каждой функции которая отображает вершины в наборы из цветов, существует такое цветовое присвоение , что для всех вершин , , и такие , что для всех ребер Vw , с (v) \ п с (ш) .k f k c v c ( v ) ∈ f ( v ) v w c ( v ) ≠ c ( w...
Теорема о четырех цветах (4CT) гласит, что каждый планарный граф имеет четыре раскраски. Есть два доказательства, представленные [Аппель, Хакен 1976] и [Робертсон, Сандерс, Сеймур, Томас 1997]. Оба эти доказательства являются компьютерными и довольно пугающими. Есть несколько гипотез в теории...
Обновление : теперь известен набор препятствий (то есть «барьер» NxM между размерами окрашиваемой и неокрашиваемой сетки) для всех четырехцветных цветов без монохроматического прямоугольника . Кто-нибудь испытывает желание попробовать 5 цветов? ;) Следующий вопрос возникает из теории Рамсея ....
Предположим, что граф с раскрасочным числом . Рассмотрим следующую игру между Алисой и Бобом. В каждом раунде Алиса выбирает вершину, и Боб отвечает цветом для этой вершины. Игра заканчивается, когда монохроматический край обнаружен. Пусть будет максимальной продолжительностью игры при оптимальной...
Предположим, что мы решили проблему подсчета правильных раскрасок путем подсчета взвешенных раскрасок следующим образом: каждая правильная раскраска получает вес 1, а каждая неправильная раскраска получает вес где c - некоторая постоянная, а v - число ребер с конечными точками, окрашенными...
Для A⊂[n]A⊂[n]A\subset [n] обозначим через aiaia_i в ithithi^{th} наименьший элемент AAA . Для двух kkk -элементных множеств A,B⊂[n]A,B⊂[n]A,B\subset [n] мы говорим, что A≤BA≤ВA\le B если ai≤biai≤bia_i\le b_i для каждого iii . kkk -равномерной Гиперграф H⊂[n]H⊂[n]{\mathcal H}\subset [n] ,...
Рассмотрим множество плоских графов, где все внутренние грани являются треугольниками. Если есть внутренняя точка нечетной степени, график не может быть трехцветным. Если каждая внутренняя точка имеет четную степень, она всегда может быть трехцветной? В идеале я хотел бы небольшой...
Рассуждая немного об этом вопросе , я попытался определить все различные причины, по которым граф может не быть k раскрашиваемым. Это единственные две причины, которые я смог определить до сих пор:G=(VG,EG)G=(VG,EG)G = (V_G,E_G)kkk содержит клику размером k + 1 . Это очевидная причина.GGGk+1k+1k+1...
Задача, которую мы здесь рассматриваем, - это расширение хорошо известной проблемы интервальной раскраски. Вместо интервалов мы рассматриваем прямоугольники, стороны которых параллельны осям. Цель состоит в том, чтобы закрасить прямоугольники минимальным количеством цветов, чтобы любые два...
Недавно я столкнулся со следующим вариантом окраски краев. Для связного неориентированного графа найдите раскраску ребер, которая использует максимальное количество цветов, а также удовлетворяет ограничению, согласно которому для каждой вершины ребра, инцидентные используют не более двух...
Извините, если это наивный вопрос, но я не смог найти оправдания ни в одном из основных учебников, таких как Бонди-Мёрти, Дистел или Уэст. У совершенных графиков есть много прекрасных свойств, но какова единственная причина, по которой их называют идеальными? Или это просто эстетическое...
3-реберная раскраска кубических графов является полной. Теорема о четырех цветах эквивалентна «Любые кубические плоские безмостовые графы раскрашиваются по 3 ребрам»NпNпNP Какова сложность 3-реберной раскраски кубических плоских графов? Также предполагается, что раскраска -edge является NP- трудной...
Проблемы окраски графа уже достаточно сложны для большинства людей . Тем не менее, мне придется столкнуться с трудностями и задать вопрос о раскраске гиперграфа. Вопрос. Какие эффективные алгоритмы существуют для нахождения приблизительно оптимальной раскраски ребер для k-равномерных гиперграфов?...
В статье «О сложности некоторых раскрасок» Бодлендер дает несколько открытых вопросов о сложности решения, имеет ли игрок 1 или 2 выигрышную стратегию в некоторых играх раскраски графов. Кто-нибудь знает, были ли они решены? 1) В одной игре два игрока по очереди выбирают одну вершину на графике и...
Я ищу небольшой граф которого векторное хроматическое число меньше хроматического числа,
Я ищу результаты твердости по раскраске вершин графов с ограниченной степенью. Учитывая граф , мы знаем, что для любого ϵ > 0 трудно приблизить χ ( G ) с множителем | V | 1 - ϵ, если NP = ZPP [ 1 ]. Но что, если максимальная степень G ограничена d ? Существуют ли в этом случае коэффициенты...
В моей работе возникает следующая проблема: Существует ли известный алгоритм, который аппроксимирует хроматическое число графа без независимого набора порядка 65? (Таким образом, альфа (G) <= 64 известна, а | V | / 64 - тривиальная нижняя, | V | тривиальная верхняя граница. Но существуют ли...
Давайте немного ослабим раскраску, то есть позволим небольшому количеству смежных вершин присваивать один и тот же цвет. Монохроматический компонент определяется как связанный компонент в подграфе, индуцированный набором вершин, которые получают один и тот же цвет, и вопрос заключается в том, чтобы...
Известно ли следующее утверждение? Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( √граммGGNnnграммGGO (...
Сложно ли приблизить приблизительное дробное хроматическое число на графах с ограниченными