Simplicial vertex

In graph theory, a simplicial vertex ${\displaystyle v}$ is a vertex whose closed neighborhood ${\displaystyle N_{G}[v]}$ in a graph ${\displaystyle G}$ forms a clique, where every pair of neighbors is adjacent to each other.^[1]

Vertex 3 (circled gray) is bisimplicial, as the set of it and its neighbors is the union of 2 cliques (denoted in black).

A vertex of a graph is bisimplicial if the set of it and its neighbours is the union of two cliques, and is k-simplicial if the set is the union of k cliques. A vertex is co-simplicial if its non-neighbours form an independent set.^[2]

Addario-Berry et al.^[3] demonstrated that every even-hole-free graph (or more specifically, even-cycle-free graph, as 4-cycles are also excluded here) contains a bisimplicial vertex, which settled a conjecture by Reed. The proof was later shown to be flawed by Chudnovsky & Seymour,^[4] who gave a correct proof. Due to this property, the family of all even-cycle-free graphs is ${\displaystyle \chi }$-bounded.

See also

• Even-hole-free graph
• ${\displaystyle \chi }$-bounded family of graphs