Тео́рия гра́фов — раздел дискретной математики, изучающий графы, одна из ветвей топологии. В самом общем смысле граф — это множество точек, которые соединяются множеством линий. Теория графов включена в учебные программы для начинающих математиков, поскольку:
- как и геометрия, обладает наглядностью;
- как и теория чисел, проста в объяснении и имеет сложные нерешённые задачи;
- не имеет громоздкого математического аппарата ;
- имеет выраженный прикладной характер.
Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.
В данном списке приводятся математические утверждения и объекты, названные именем венгерского математика Пала Эрдёша.
Гипотеза Эрдёша — Бура — математическая проблема, касающаяся числа Рамсея на разреженных графах. Гипотеза названа в честь Пала Эрдёша и Стефана Бура. Гипотеза утверждает, что число Рамсея в любом семействе разреженных графов должно иметь почти линейный рост в зависимости от числа вершин графа.
Граф Радо — единственный счётный граф R, такой, что для любого конечного графа G и его вершины v любое вложение G − v в R в качестве порождённого подграфа может быть расширено до вложения G в R. Как результат граф Радо содержит все конечные и счётные бесконечные графы в качестве подграфов. Граф Радо известен также под именами случайный граф и граф Эрдёша — Реньи.
В теории графов графом пересечений называется граф, представляющий схему пересечений семейства множеств. Любой граф можно представить как граф пересечений, но некоторые важные специальные классы можно определить посредством типов множеств, используемых для представления в виде пересечений множеств.
В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.
Вероятностный метод — неконструктивный метод доказательства существования математического объекта с заданными свойствами. В основном используется в комбинаторике, но также и в теории чисел, линейной алгебре и математическом анализе, а также в информатике и теории информации.
Число пересечений графа — наименьшее число элементов в представлении данного графа как графа пересечений конечных множеств, или, эквивалентно, наименьшее число клик, необходимых для покрытия всех рёбер графа.
В теории графов разрезающее циклы множество вершин графа — это множество вершин, удаление которых приводит к разрыву циклов. Другими словами, разрезающее циклы множество вершин содержит по меньшей мере по одной вершине из любого цикла графа. Задача о разрезающем циклы множестве вершин является в теории вычислительной сложности NP-полной задачей. Задача входит в список 21 NP-полных задач Карпа. Задача имеет широкое применение в операционных системах, базах данных и разработке СБИС.
Теорема Робертсона — Сеймура утверждает, что любое семейство графов, замкнутое относительно операций удаления и стягивания рёбер, может быть определено конечным набором запрещённых графов.
Критический граф — граф, в котором удаление любой вершины или ребра приводит к уменьшению хроматического числа графа.
Теорема о планарном разбиении — это форма изопериметрического неравенства для планарных графов, которое утверждает, что любой планарный граф может быть разбит на более мелкие части путём удаления небольшого числа вершин. В частности, удалением O(√n) вершин из графа с n вершинами можно разбить граф на несвязные подграфы, каждый из которых имеет не более 2n/3 вершин.
Теорема о совершенных графах Ловаша утверждает, что неориентированный граф является совершенным тогда и только тогда, когда его дополнение также совершенно. Это утверждение высказал в виде гипотезы Берж и утверждение называют иногда слабой теоремой о совершенных графах, чтобы не смешивать со строгой теоремой о совершенных графах, описывающей совершенные графы их запрещёнными порождёнными подграфами.
Теорема де Брёйна — Эрдёша — теорема теории графов доказанная Палом Эрдёшем и Николаасом де Брёйном.
Граф дружеских отношений Fn — это планарный неориентированный граф с 2n+1 вершинами и 3n рёбрами.
Гипотеза Эрдёша — Хайналя утверждает, что семейства графов, определяемые запрещёнными порождёнными подграфами, имеют либо большие клики, либо большие независимые множества. Точнее, для произвольного неориентированного графа 
пусть 
является семейством графов, не содержащих в качестве порождённого подграфа. Тогда, согласно гипотезе, существует константа 
такая, что графы с 
вершинами в имеют либо клику, либо независимое множество размером 
.
Гипотеза Эрдёша — Фабера — Ловаса — это проблема о раскраске графов, названная именами Пала Эрдёша, Ванса Фабера и Ласло Ловаса, которые сформулировали её в 1972 году. Гипотеза гласит:
- Если k полных графов, каждый из которых имеет в точности k вершин, обладают свойством, что любая пара полных графов имеет не более одной общей вершины, то объединение графов может раскрашено в k цветов.
