Двудольные графы, критерий двудольности. Вершинные и реберные раскраски графа. Простейшие свойства раскрасок. Теорема Брукса. Теоремы Визинга и Гупты (б/д). Совершенные графы. Слабая и сильная гипотезы Бержа: доказательство слабой гипотезы.