В теории графов граф Хенсона G i является неориентированным бесконечным графом , единственным счетным однородным графом , который не содержит клику i -вершин , но содержит все K i -свободные конечные графы как индуцированные подграфы. Например, G 3 является графом без треугольников , который содержит все конечные графы без треугольников.
Эти графы названы в честь К. Уорда Хенсона, который опубликовал их конструкцию (для всех i ≥ 3 ) в 1971 году. [1] Первый из этих графов, G 3 , также называется однородным графом без треугольников или универсальным графом без треугольников .
Для построения этих графов Хенсон упорядочивает вершины графа Радо в последовательность со свойством, что для любого конечного множества вершин S существует бесконечно много вершин, имеющих S в качестве множества своих более ранних соседей. (Существование такой последовательности однозначно определяет граф Радо.) Затем он определяет G i как индуцированный подграф графа Радо, образованный путем удаления последней вершины (в порядке последовательности) каждой i -клики графа Радо. [1]
При такой конструкции каждый граф G i является индуцированным подграфом G i + 1 , а объединение этой цепочки индуцированных подграфов является самим графом Радо. Поскольку каждый граф G i исключает по крайней мере одну вершину из каждой i -клики графа Радо, в G i не может быть i -клики .
Любой конечный или счетный граф H без i -клик может быть найден как индуцированный подграф графа G i путем его построения по одной вершине за раз, на каждом шаге добавляя вершину, более ранние соседи которой в G i совпадают с множеством более ранних соседей соответствующей вершины в H. То есть, G i является универсальным графом для семейства графов без i -клик.
Поскольку существуют i -клико-свободные графы произвольно большого хроматического числа , графы Хенсона имеют бесконечное хроматическое число. Более строго, если граф Хенсона G i разбит на любое конечное число индуцированных подграфов, то по крайней мере один из этих подграфов включает все i -клико-свободные конечные графы как индуцированные подграфы. [1]
Подобно графу Радо, G 3 содержит двунаправленный гамильтонов путь , такой что любая симметрия пути является симметрией всего графа. Однако это неверно для G i , когда i > 3 : для этих графов каждый автоморфизм графа имеет более одной орбиты. [1]