Раскраска вершин графа. Определение. Пусть – произвольное множество элементов, называемых цветами или красками, тогда отображение

Определение. Пусть – произвольное множество элементов, называемых цветами или красками, тогда отображение , где – множество вершин графа , называется раскраской вершин графа.

Раскраска называется правильной, если для любого ребра .

Определение. Граф – раскрашиваем, если его можно правильно раскрасить -цветами.

Если граф – раскрашиваем, но его нельзя правильно раскрасить цветом, граф называется – хроматическим, в этом случае – хроматическое число графа .

Граф , например, – хроматический, любой двудольный граф 2-хроматический.