Хроматическое число

---

Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета.

Формально, хроматическое число — минимальное число ${\displaystyle k}$, такое что множество ${\displaystyle V}$ вершин графа ${\displaystyle G}$ можно разбить на ${\displaystyle k}$ непересекающихся классов ${\displaystyle C_{1},C_{2},\ldots ,C_{k}}$:

таких, что вершины в каждом классе независимы, то есть любое ребро графа не соединяет вершины одного и того же класса. Стандартное обозначение — ${\displaystyle \chi (G)}$.

${\displaystyle k}$-раскрашиваемый граф — граф, хроматическое число которого не превосходит ${\displaystyle k}$, то есть его вершины можно раскрасить не более чем ${\displaystyle k}$ цветами так, что у любого ребра концы будут разного цвета. ${\displaystyle k}$-хроматический граф — граф, хроматическое число которого равно ${\displaystyle k}$, то есть вершины графа можно раскрасить ${\displaystyle k}$ цветами так, что у любого ребра концы будут разного цвета, но так раскрасить ${\displaystyle k-1}$ цветами — уже нельзя.

Множество глубоких задач теории графов легко формулируются в терминах раскраски. Самая знаменитая из таких задач, проблема четырёх красок, в настоящее время решена, однако появляются новые, например, обобщение проблемы четырёх красок, гипотеза Хадвигера.

Хроматический класс графа ${\displaystyle G}$ — минимальное число цветов, в которые можно раскрасить ребра графа ${\displaystyle G}$ так, чтобы смежные ребра имели разные цвета. Обозначается ${\displaystyle \chi '(G)}$. Проблема реберной раскраски произвольного плоского кубического графа без мостов тремя цветами эквивалентна знаменитой Проблеме четырёх красок. Рёберная раскраска определяет 1-факторизацию графа.

---