В теории графов смежной вершиной вершины v называется вершина, соединённая с v ребром. Окрестностью вершины v в графе G называется порождённый подграф графа G, состоящий из всех вершин, сопряжённых v и всех рёбер, соединяющих две такие вершины. Например, рисунок показывает граф с 6 вершинами и 7 рёбрами. Вершина 5 смежна вершинам 1, 2 и 4, но не смежна вершинам 3 и 6. Окрестность вершины 5 — это граф с тремя вершинами 1, 2 и 4, и одним ребром, соединяющим вершины 1 и 2.
В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.
Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского . Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число. Мычельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера.
В теории графов расщепляемым графом называется граф, в котором вершины можно разделить на клику и независимое множество. Расщепляемые графы впервые изучали Фёлдес и Хаммер, и независимо ввели Тышкевич и Черняк.
Жадная раскраска в теории графов — раскраска вершин неориентированного графа, созданная жадным алгоритмом, который проходит вершины графа в некоторой предопределённой последовательности и назначает каждой вершине первый доступный цвет. Жадные алгоритмы, в общем случае, не дают минимально возможное число цветов, однако они используются в математике в качестве техники доказательств других результатов, относящихся к раскраске, а также в компьютерных программах для получения раскраски с небольшим числом цветов.
Флаговый комплекс — симплициальный комплекс, в котором любой набор вершин, попарно соединённых рёбрами, образует симплекс.
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани.
В теории графов пороговый граф — это граф, который может быть построен из одновершинного графа последовательным выполнением следующих двух операций:
- Добавление в граф одной изолированной вершины
- Добавление одной доминирующей вершины в граф, т.е. отдельной вершины, связанной со всеми остальными вершинами.
В теории графов дистанционно-наследуемый граф — это граф, в котором расстояния в любом связном порождённом подграфе те же самые, что и в исходном графе. Таким образом, любой порождённый подграф наследует расстояния большего графа.
Жёсткость графа — мера связности графа: граф G t-жёсток при некотором вещественном t, если для любого целого k > 1 нельзя разбить граф G на k различных компонент связности путём удаления менее чем tk вершин. Например, граф 1-жёсток, если число компонент, образующихся при удалении вершин, всегда не превосходит числа удалённых вершин. Жёсткость графа — это максимальное t, для которого он t-жёсток. Число является конечным числом для всех конечных графов, за исключением полных графов, которые, по соглашению, имеют бесконечную жёсткость.
В теории графов вполне упорядочиваемый граф — это граф, вершины которого можно упорядочить так, что алгоритм жадной раскраски с этим упорядочением оптимально раскрашивает любой порождённый подграф заданного графа. Соответствующее упорядочение называется совершенным. Вполне упорядочиваемые графы образуют подкласс совершенных графов и в это подкласс входят хордальные графы, графы сравнимости и дистанционно-наследуемые графы. Однако проверка, является ли граф вполне упорядочиваемым, есть NP-полная задача.
В теории графов говорят, что граф G гипогамильтонов, если сам по себе граф не имеет гамильтонова цикла, но любой граф, полученный удалением одной вершины из G, является гамильтоновым.
Универсальный граф — это бесконечный граф, содержащий любой конечный граф в качестве порождённого подграфа. Универсальный граф этого типа первым построил Р. Радо и этот граф теперь называется графом Радо или случайным графом. Более свежие работы фокусируются на универсальных графах для семейства графов F. То есть бесконечный граф, принадлежащий F, содержащий все конечные графы семейства F. Например, графы Хэнсона являются универсальными в этом смысле для графов без i-клик.
Индифферентный граф — это неориентированный граф, построенный путём назначения вещественного числа каждой вершине и соединения двух вершин ребром, когда их числа отличаются не более чем на единицу. Индифферентные графы являются также графами пересечений множеств единичных отрезков или интервалов с определённым свойством вложения. Основываясь на этих двух типах интервальных представлений, эти графы называются также графами единичных отрезков или собственными интервальными графами. Индифферентные графы образуют подкласс интервальных графов.
Тривиально совершенный граф — это граф со свойством, что в каждом его порождённом подграфе размер максимального независимого множества равен числу максимальных клик. Тривиально совершенные графы первым изучал Волк, но название дал Голумбик. Голумбик писал, что «это название было выбрано ввиду тривиальности доказательства, что такие графы являются совершенными.» Тривиально совершенные графы известны также как графы сравнимости деревьев, древовидные графы сравнимости и квазипороговые графы.
Сильная гипотеза о совершенных графах — это характеризация запрещёнными графами совершенных графов как в точности тех графов, которые не имеют ни нечётных дыр, ни нечётных антидыр. Гипотезу высказал Берж в 1961. Доказательство Марии Чудновской, Нейла Робертсона, Пола Сеймура и Робина Томаса было заявлено в 2002 и опубликовано ими в 2006.
Выигрышный граф полицейского — это неориентированный граф, на котором преследователь (полицейский) может выиграть игру преследования-уклонения, в которой он преследует грабителя и игроки поочерёдно делают передвижения вдоль рёбер графа или стоят на месте пока, полицейский не займёт вершину, на которой находится грабитель. Конечные выигрышные графы полицейского называются также разбираемыми графами или конструируемыми графами, поскольку они могут быть разобраны путём удаления раз за разом доминируемой вершины или построены путём повторяющегося добавления такой вершины. Выигрышные графы полицейского могут быть распознаны за полиномиальное время жадным алгоритмом, который создаёт порядок разборки. В этот класс входят хордальные графы и графы, содержащие универсальную вершину.
Квадратичный граф — граф, в котором все вершины имеют степень 4. Другими словами, квадратичный граф является 4-регулярным графом.
Гипотеза Харборта утверждает, что любой планарный граф имеет планарное представление, в котором каждое ребро является отрезком целочисленной длины. Эта гипотеза носит имя Хайко Харборта и усилила бы теорему Фари о существовании рисунка с прямолинейными рёбрами для любого планарного графа. По этой причине рисунок графа с целочисленными длинами рёбер известен также как целочисленное вложение Фари. Не смотря на многочисленные исследования в этом направлении гипотеза остаётся открытой.
