Сложность раскраски ребер в плоских графах

15

3-реберная раскраска кубических графов является полной. Теорема о четырех цветах эквивалентна «Любые кубические плоские безмостовые графы раскрашиваются по 3 ребрам»Nп

Какова сложность 3-реберной раскраски кубических плоских графов?

Также предполагается, что раскраска -edge является NP- трудной для плоских графов с максимальной степенью \ Delta \ in {4,5}.Н РΔNпΔ∈

Был ли достигнут какой-либо прогресс в разрешении этой гипотезы?

Марек Хробак и Такао Нишизеки. Улучшены алгоритмы раскраски ребер для плоских графов. Журнал Алгоритмов, 11: 102-116, 1990

cc.complexity-theory graph-theory np-hardness graph-colouring Мухаммед Аль-Туркистани
источник
Разве строка 2 в таблице 1 в dx.doi.org/10.1007/s00453-007-9044-3 не означает, что «3- реберная раскраска кубических плоских графов» полиномиально разрешима?
Александр Бондаренко
Запись в таблице относится к раскрашивающей бумаге Робертсона, Сандерса, Сеймура и Томаса Четыре, в которой рассматриваются кубические планарные графы без мостов .
Мухаммед Аль-Туркистани
+1 отличный вопрос, у меня есть симлиар, но более практичный ...
draks ...
Привет, вы знаете, есть ли прогресс в раскраске 3-ребер на кубических графах на двойном торе ?
Дракс ...

Ответы:

15

Каждый плоский мост без мостов может быть трехцветным за квадратичное время, так как эта задача эквивалентна четырехцветному плоскому графу, который можно выполнить за квадратичное время. (См. Робертсон, Сандерс, Сеймур и Томас: http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps )

РЕДАКТИРОВАТЬ: Как указывает Матье, кубические графы с мостами никогда не окрашиваются в 3 ребра.

Эмиль
источник
5
Кубические графы с мостом никогда не окрашиваются в 3 ребра. Это следует из «Леммы о четности», например, см. Примечание под леммой 2.1 в combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Колин Маккуиллан,
1
Чтобы быть точным, эквивалентность между краевой окраской и 4- окраской означает только кубические планарные графы без мостов . 34
Матье Шапель
@ Эмиль, я не понимаю, как это могло бы означать, что кубические графы PLANAR с мостами никогда не окрашиваются в 3 ребра.
Мухаммед Аль-Туркистани
@ MohammadAl-Turkistany Учитывая два цвета a и b в d-ребристой раскраске d-регулярного графа (d> = 2), подграф, индуцированный ребрами, окрашенными a или b, является несвязным объединением четных циклов. Из этого следует лемма о четности: если X - собственное непустое подмножество V (G), а F - разрез, индуцированный X, то для всех цветов a и b четность числа ребер X, окрашенных a, равна равен четности числа ребер X окрашенного б. Следовательно, любой d-регулярный граф (d> = 2) с мостом не может быть окрашен в d-ребро, независимо от того, является он плоским или нет.
Леандро Затеско
5

3-реберная раскраска графов без треугольников с максимальной степенью 3 также является NP-полной, см. 10.1016 / S0096-3003 (96) 00021-5.

Diamantis Koreas
источник