vértice simplicial

En teoría de grafos , un vértice simplicial${\displaystyle v}$es un vértice cuyo vecindario cerrado${\displaystyle N_{G}[v]}$en un gráfico${\displaystyle G}$forma una camarilla , donde cada par de vecinos es adyacente entre sí. ^{[ 1 ]}

Un vértice de un grafo es bisimplicial si el conjunto formado por él y sus vecinos es la unión de dos cliques, y es k - simplicial si el conjunto es la unión de k cliques. Un vértice es cosimplicial si sus no vecinos forman un conjunto independiente . ^{[ 2 ]}

Addario-Berry et al. ^{[ 3 ]} demostraron que todo grafo par sin agujeros (o más específicamente, grafo par sin ciclos , ya que los 4-ciclos también se excluyen aquí) contiene un vértice bisimplicial, lo que resolvió una conjetura de Reed. Posteriormente, Chudnovsky y Seymour ^{[ 4 ]} demostraron que la prueba era errónea y proporcionaron una demostración correcta. Debido a esta propiedad, la familia de todos los grafos pares sin ciclos es${\displaystyle \chi }$-limitado .

• Gráfico sin agujeros pares
• ${\displaystyle \chi }$-familia acotada de grafos