Недружественный раздел

Нерешенная задача по математике :

Каждый ли счетный граф имеет недружественное разбиение на две части?

В математике бесконечных графов недружественное разбиение или мажоритарная раскраска — это разбиение вершин графа на непересекающиеся подмножества, так что каждая вершина имеет по крайней мере столько же соседей в других множествах, сколько она имеет в своем собственном множестве. Это обобщение концепции максимального разреза для конечных графов, который автоматически является недружественным разбиением. (В противном случае вершина с большим количеством соседей в ее собственном наборе может быть перемещена в другой набор, увеличивая количество разрезаемых ребер.) Гипотеза о недружественном разбиении - это нерешенная проблема, заключающаяся в том, что каждый счетный граф имеет недружественное разбиение на два подмножества. ^{[ 1 ]}

Роберт Х. Коуэн и Уильям Р. Эмерсон в неопубликованной работе предположили, что каждый бесконечный граф имеет недружественное разбиение на два подмножества. Однако Сахарон Шела и Эрик Чарльз Милнер опровергли эту гипотезу, показав, что несчетные графы могут не иметь недружественных разделов на два подмножества. Тем не менее они показали, что недружественное разделение на три подмножества всегда существует. ^{[ 2 ]}

Среди счетных графов существование недружественного разбиения на два подмножества известно для следующих частных случаев:

Графы, имеющие конечное число вершин бесконечной степени. ^{[ 3 ]}
Графы, в которых все вершины имеют бесконечную степень, с помощью аргумента, использующего метод туда и обратно. ^{[ 1 ]}
Графики без конца ^{[ 4 ]}
Графы без подразделения бесконечной клики ^{[ 5 ]}

Вопрос о произвольных счетных графах остается открытым. ^{[ 1 ]}

Ссылки

^ Jump up to: ^а ^б ^с ДеВос, Мэтью (22 октября 2007 г.), «Недружественные разделы» , Открытый проблемный сад
^ Шела, Сахарон ; Милнер, EC (1990), «Графы без недружественных разделов» (PDF) , у Бейкера, А.; Боллобас, Б.; Хайнал, А. (ред.), Дань памяти Полу Эрдешу , Cambridge University Press, стр. 373–384, doi : 10.1177/016502549001300309 , MR 1117030 , S2CID 143480036
^ Аарон, Р.; Милнер, ЕС; Прикры К. (1990), «Недружественные разбиения графа», Журнал комбинаторной теории , серия B, 50 (1): 1–10, doi : 10.1016/0095-8956(90)90092-E , MR 1070461
^ Брюн, Хеннинг; Дистель, Рейнхард; Георгакопулос, Агелос; Шпруссель, Филипп (2010), «Каждый безлучевой граф имеет недружественный раздел», Combinatorica , 30 (5): 521–532, doi : 10.1007/s00493-010-2590-3 , MR 2776717 , S2CID 9304176
^ Бергер, Эли (2017), «Недружественные разделы для графов, не содержащих подразделения бесконечной клики», Combinatorica , 37 (2): 157–166, doi : 10.1007/s00493-015-3261-1 , MR 3638340 , S2CID 254028041

[garden-1] Jump up to: ^а ^б ^с ДеВос, Мэтью (22 октября 2007 г.), «Недружественные разделы» , Открытый проблемный сад

[shemil-2] Шела, Сахарон ; Милнер, EC (1990), «Графы без недружественных разделов» (PDF) , у Бейкера, А.; Боллобас, Б.; Хайнал, А. (ред.), Дань памяти Полу Эрдешу , Cambridge University Press, стр. 373–384, doi : 10.1177/016502549001300309 , MR 1117030 , S2CID 143480036

[amp-3] Аарон, Р.; Милнер, ЕС; Прикры К. (1990), «Недружественные разбиения графа», Журнал комбинаторной теории , серия B, 50 (1): 1–10, doi : 10.1016/0095-8956(90)90092-E , MR 1070461

[bdgs-4] Брюн, Хеннинг; Дистель, Рейнхард; Георгакопулос, Агелос; Шпруссель, Филипп (2010), «Каждый безлучевой граф имеет недружественный раздел», Combinatorica , 30 (5): 521–532, doi : 10.1007/s00493-010-2590-3 , MR 2776717 , S2CID 9304176

[berger-5] Бергер, Эли (2017), «Недружественные разделы для графов, не содержащих подразделения бесконечной клики», Combinatorica , 37 (2): 157–166, doi : 10.1007/s00493-015-3261-1 , MR 3638340 , S2CID 254028041

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]