Граф Генсона — це неорієнтований нескінченний граф, єдиний зліченний однорідний граф, що не містить клік з вершинами, але містить як підграфи всі вільні від графи. Наприклад, є графом без трикутників, що містить усі скінченні вільні від трикутників графи.
Графи названо ім'ям К. Ворда Генсона, який опублікував їх побудову 1971 року (для всіх ). Перший із цих графів називають однорідним вільним від трикутників графом або універсальним вільним від трикутників графом.
Побудова Для побудови цих графів Генсон упорядковує вершини графа Радо в послідовність із властивістю, що для будь-якої скінченної множини вершин існує нескінченно багато вершин, що мають як множину найраніших сусідів (існування такої послідовності єдиним чином визначає граф Радо). Потім він визначає як породжений підграф графа Радо, утворений видаленням кінцевих вершин (у вибраному порядку) будь-якої -кліки графа Радо.
За такої побудови будь-який граф є породженим підграфом графа , а об'єднанням цього ланцюжка підграфів є сам граф Радо. Оскільки в будь-якому графі виключено щонайменше одну вершину -кліки графа Радо, в не може бути -клік.
Універсальність Будь-який скінченний або зліченний вільний від -клік граф можна знайти як породжений підграф графа послідовним додаванням вершин, раніші вершини яких у відповідають множині раніших сусідів відповідних вершин в . Таким чином, є універсальним графом для сімейства вільних від -клік графів.
Оскільки існують вільні від -клік графи з довільно великим хроматичним числом, граф Генсона має нескінченне хроматичне число. Строгіше, якщо граф Генсона розбити на будь-яке скінченне число породжених підграфів, то щонайменше один з цих графів включає всі вільні від -клік скінченні графи як породжені підграфи.
Симетрія Подібно до графа Радо, граф містить двонаправлений гамільтонів шлях, такий, що будь-яка симетрія шляху є симетрією всього графа. Однак це не так для , коли — для цих графів будь-який автоморфізм графа має більше однієї орбіти.
Примітки
Література