Причины, по которым график может быть не

21

Рассуждая немного об этом вопросе , я попытался определить все различные причины, по которым граф может не быть k раскрашиваемым. Это единственные две причины, которые я смог определить до сих пор:G=(VG,EG)k

  1. содержит клику размером k + 1 . Это очевидная причина.Gk+1
  2. Существует подграф группы G такой, что оба следующих утверждения верны:H=(VH,EH)G

    • не k - 1 раскраска.Hk1
    • . Другими словамисуществуетузле х в G , но не в H , такойчто х соединен с каждым узлом в H .xVGVH yVH {x,y}EGxGHxH

Мы можем видеть две причины выше, как правила. К рекурсивно их применения, только два пути , чтобы построить не Colorable граф , который не содержит к + 1 клика:kk+1

  1. Начните с цикла четной длины (который равен цветам), затем примените правило 2 для k - 1 раз. Обратите внимание, что ребро не считается циклом длины 2 (в противном случае этот процесс приведет к созданию клики k + 1 ).2k12k+1
  2. Начните с цикла нечетной длины (который равен цветам), затем примените правило 2 для k - 2 раза. Длина начального цикла должна быть больше 3 (в противном случае этот процесс приведет к созданию клики k + 1 ).3k23k+1

Вопрос

Есть ли еще какая-то причина, кроме указанных выше, которая делает граф не раскрашиваемым?k

 
Обновление 30/11/2012

Точнее, мне нужна некоторая теорема вида:

Граф имеет хроматическое число χ ( G ) = k + 1 тогда и только тогда, когда ...Gχ(G)=k+1

Исчисление Хайоса , на которое указал Ювал Фильмус в своем ответе, является прекрасным примером того, что я ищу, поскольку граф имеет хроматическое число χ ( G ) = k + 1 тогда и только тогда, когда его можно вывести из аксиомы K k. + 1 путем многократного применения 2 правила вывода исчисления. Тогда число Хайоса h ( G ) - это минимальное количество шагов, необходимых для получения G (т. Е. Длина кратчайшего доказательства).Gχ(G)=k+1Kk+1h(G)G

Это очень интересно, что:

  • Вопрос о том, существует ли граф чье h ( G ) экспоненциально по размеру G , остается открытым.Gh(G)G
  • Если такая не существует, то Н Р = C уплотнительное N P .GNP=coNP
Джорджо Камерани
источник
5
Я повторю свой комментарий на вопрос, на который вы ссылаетесь, в случае, если вы не знаете теорему (о которой все думают о раскраске) ​​Эрдеша: учитывая натуральные числа g и k, существует график с обхватом не менее g и хроматическим число не менее k. Обхват графика - это размер наименьшего цикла, что означает, что если у вас есть обхват не менее 3, то каждая максимальная клика имеет размер 2 (каждое ребро является максимальной кликой).
Пол GD
2
Простое наблюдение, которое часто полезно: каждый цветовой класс является независимым набором. Если вы можете показать, что нет большого независимого набора, то вы знаете, что вам понадобится много цветов.
Юкка Суомела
1
Если бы всегда была простая причина того, что графы не являются -раскрашиваемыми, задача раскраски графов не была бы NP-трудной. Если P = NP, некоторые графы не являются k- раскрашиваемыми только потому, что . kk
Джефф
5
@ Jɛ ff E: причина может быть простой, но трудно вычислить. Есть довольно простая причина, почему граф имеет или не имеет клик, но он все еще NP-труден. k
Люк Мэтисон

Ответы:

29

Вы должны проверить исчисление Хайос . Хайос показал, что у каждого графа с хроматическим числом, по крайней мере, есть подграф, у которого есть «причина», требующая k цветов. Рассматриваемая причина - система доказательства для требования k цветов. Единственная аксиома - это K k , и есть два правила вывода. См. Также эту статью Питасси и Уркхарта об эффективности этой системы доказательств.kkkKk

Юваль Фильмус
источник
1
Отлично, это то, что я искал.
Джорджио Камерани
1
Спасибо за указатель. Не знал о строительстве Hajos ранее.
Чандра Чекури
15

Частичный ответ в том, что я не знаю хорошей «причины», которую можно обобщить, но следующий график ( отсюда беззастенчиво ):

Не раскрашиваемый граф без K4 или нечетного цикла с полностью связным соседом

Не является 3-раскрашиваемым, но, очевидно, 4-раскрашиваемым (будучи плоским) и не содержит ни , ни какого-либо цикла с дополнительной вершиной, связанной со всеми вершинами цикла (если я что-то не пропустил, но только вершины) связаны с вершиной и ее сосед в 3-циклах). Если пойти дальше, вы можете применить версию правила 2, чтобы получить график хроматического числа 5.K4

Я подозреваю, что для любого данного рода есть график определенного минимального хроматического числа (см. Гипотезу Хивуда ), который не следует правилам 1 или 2. Конечно, у меня нет никаких доказательств, кроме интуиции.

Люк Мэтисон
источник
K4
1
kKk
Kkk1
5
Kk
12

Ловаш нашел топологические препятствия для k-окрашивания и использовал свою теорию для решения гипотезы Кназера. Его теорема состоит в следующем. Пусть G - связный граф, и пусть N (G) - симплициальный комплекс, грани которого являются подмножествами V, имеющими общих соседей. Тогда, если N (K) является k-связным (а именно, все его приведенные группы гомологий равны от 0 до размерности k-1), то количество цветов, необходимых для окраски G, составляет не менее k + 3.

Гил Калай
источник
11

Отсутствие большого независимого набора может быть так же важно, как и большая клика.

Важным препятствием для того, чтобы граф не был k-раскрашиваемым, является то, что максимальный размер независимого множества меньше, чем n / k, где n - количество вершин. Это очень важное препятствие. Например, это означает, что случайный граф в G (n, 1/2) имеет хроматическое число, по крайней мере, n / log n.

Более сложное препятствие состоит в том, что для каждого назначения неотрицательных весов для вершин не существует независимого набора, который бы занимал долю 1/5 (или более) от общего веса. Обратите внимание, что это также включает в себя «никаких препятствий клика». LP-двойственность говорит вам, что это препятствие эквивалентно тому, что «дробное хроматическое число» G больше k.

Существуют также препятствия для k-окрашивания другой природы, которые иногда выходят за пределы дробного барьера хроматических чисел. Я посвящу им отдельный ответ.

Гил Калай
источник
Спасибо за Ваш ответ! Более изысканные веса связывания препятствий и независимые множества чрезвычайно интересны ...
Джорджо Камерани
11

Gχ(G)=k+1

Gχ(G)kGk1

Дэвид Эппштейн
источник
Благодарность! Это определенно на 100% адекватно. Это идеально подходит для переформулировки вопроса.
Джорджио Камерани