Сколько вершин удалить, что граф стал хроматическим?

[xellos]

Не могу ни решить, ни найти источник с решением следующей задачи в общем виде.

Дано: определённым образом окрашенный граф.
Найти: минимальное число вершин, после удаления которых граф станет хроматическим (т.е., чтобы концы каждого из ребер были окрашены в разные цвета).

-- 30.01.2013, 16:35 --

Для частных случаев графов и их окрасок решить, естественно, удается. А вот как решать в общем виде?

[xellos]

Всё ещё жду какой-либо помощи. Буду рад любым комментариям.

[jrock]

Попробуйте сделать док-во примерно так: сделайте оценку снизу, потом оценку сверху. Потом покажите что они совпадают.

[xellos]

Хм, любопытный путь. А как делаются подобные оценки?

[jrock]

Ну можно посмотреть док-во т.Кенинга
https://dl.dropbox.com/u/15433464/grafin.pdf на стр.7.

У меня нет в голове примера проще.

Могу попробовать.
Решим задачу: докажите, что если в если было $n$ свадеб, то было $n$ мужей и $n$ жен.
Попробуем доказать от противного: пусть мужей было строго больше $n$. Тогда если было $n$ свадеб, то какой-то жене досталось два мужа по принципу Дирихле, значит, мужей $\le n$.
Обратно, пусть межей строго меньше $n$, тогда какому-то мужу досталось две жены, опять же, по принципу Дирихле.
Значит, мужей было $\ge n$ и $\le n$ одновременно. Значит, мужей было ровно $n$ штук.