En la teoría de grafos , el Henson gráfico G i es un no dirigido gráfico infinito , el contable único gráfico homogéneo que no contiene un i -vertex clique pero que contiene todos los K i -free grafos finitos como subgrafos inducidos. Por ejemplo, G 3 es un gráfico sin triángulos que contiene todos los gráficos sin triángulos finitos.
Estos gráficos llevan el nombre de C. Ward Henson, quien publicó una construcción para ellos (para todo i ≥ 3 ) en 1971. [1] El primero de estos gráficos, G 3 , también se llama el gráfico homogéneo sin triángulos o el universal gráfico sin triángulos .
Para construir estos gráficos, Henson ordena los vértices del gráfico de Rado en una secuencia con la propiedad de que, por cada conjunto finito S de vértices, hay infinitos vértices que tienen a S como su conjunto de vecinos anteriores. (La existencia de tal secuencia define de forma única el gráfico de Rado.) Luego define G i como el subgrafo inducido del gráfico de Rado formado al eliminar el vértice final (en el orden de secuencia) de cada i- clique del gráfico de Rado. [1]
Con esta construcción, cada gráfico G i es un subgrafo inducido de G i + 1 , y la unión de esta cadena de subgrafos inducidos es el propio gráfico de Rado. Debido a que cada gráfico G i omite al menos un vértice de cada i- círculo del gráfico de Rado, no puede haber i- círculo en G i .
Cualquier grafo H finito o contable libre de clicas i se puede encontrar como un subgrafo inducido de G i construyéndolo un vértice a la vez, en cada paso agregando un vértice cuyos vecinos anteriores en G i coincidan con el conjunto de vecinos anteriores del vértice correspondiente en H . Es decir, G i es un gráfico universal para la familia de gráficos libres de i -clique.
Debido a que existen i gráficos -clique libres de arbitrariamente grande número cromático , los gráficos tienen Henson número cromática infinita. Más fuertemente, si un gráfico de Henson G i se divide en cualquier número finito de subgrafos inducidos, entonces al menos uno de estos subgrafos incluye todos los grafos finitos libres de i -clique como subgrafos inducidos. [1]