Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
Хромати́ческое число графа — минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы концы любого ребра имели разные цвета.
Хроматический многочлен — многочлен, изучаемый в алгебраической теории графов, представляющий число раскрасок графа как функцию от числа цветов. Первоначально определён Джорджем Биркгофов для попытки решения на проблемы четырёх красок. Обобщен и систематически изучен Хасслером Уитни, Татт обобщил хроматический многочлен до многочлена Татта, связав его с моделью Поттса статистической физики.
Задача Нелсона — Эрдёша — Хадвигера — задача комбинаторной геометрии, первоначально поставленная как задача о раскраске или хроматическом числе евклидова пространства.
В теории графов тотальной раскраской называется вид раскраски вершин и рёбер графа. Если не указано явно другое, тотальная раскраска предполагается правильной в том смысле, что никакие смежные вершины и никакие смежные рёбра и вершины, лежащие на концах рёбер, не раскрашиваются в один и тот же цвет.
Дробная раскраска — это тема молодой области теории графов, известной как теория дробных графов. Дробная раскраска является обобщением обычной раскраски. В традиционной раскраске графа каждой вершине назначается некий цвет, и смежным вершинам — тем, что связаны рёбрами, — должны быть назначены разные цвета. В дробной раскраске каждой вершине назначается набор цветов. Ограничения, накладываемые на смежные вершины, остаются в силе, так что если две вершины соединены ребром, они не должны иметь общих цветов.
Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов, его обхват по определению равен бесконечности. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.
В теории графов гармоническая раскраска — это (правильная) раскраска вершин, при которой любая пара цветов появляется на смежных вершинах не более одного раза. Гармоническое хроматическое число χH(G) графа G — это минимальное число цветов, необходимых для гармонической раскраски графа G.
Построение Хайоша — это операция над графами, названная именем венгерского математика Дьёрдя Хайоша, которая может быть использована для построения любого критического графа или любого графа, хроматическое число которого не меньше некоторого заданного порога.
Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа 
с обозначением 
можно определить следующими эквивалентными способами.
- равен инфимуму по всем вещественным числам
таким, что существует отображение из 
в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии 
вдоль окружности. - равен инфимуму по рациональным числам
таким, что существует отображение из в циклическую группу 
со свойством, что смежные вершины отображаются в элементы на расстоянии 
друг от друга. - В ориентированном графе определим дисбаланс цикла
, как значение 
, делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, равен минимальному дисбалансу по всем ориентациям графа .
Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое
- правильное — никакие две смежные вершины не получают один и тот же цвет,
- сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали.
Гипотеза Хедетниеми — математическая гипотеза, в общем случае опровергнутая, предположение о связи между раскраской графов и тензорным произведением графов:
,
Предписанная раскраска — это вид раскраски графов, в которой каждая вершина может принимать ограниченное множество допустимых цветов. Одними из первых эту раскраску изучили Визинг и Эрдёш, а также Рубин и Тейлор в 1970-х годах.
Смешанный граф G = представляет собой математический объект, состоящий из набора вершин V, набора (неориентированных) ребер E и набора направленных ребер A.
