Simplicial vertex

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

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]

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

References

1. Agnarsson, Geir; Halldórsson, Magnús M. (October 2007). "Strongly simplicial vertices of powers of trees". Discrete Mathematics. 307 (21): 2647–2652. doi:10.1016/j.disc.2007.01.002.
2. Hoàng, Chính T.; Hougardy, Stefan; Maffray, Frédéric; Mahadev, N. V. R. (29 March 2004). "On simplicial and co-simplicial vertices in graphs". Discrete Applied Mathematics. 138 (1–2): 117–132. doi:10.1016/S0166-218X(03)00275-0.
3. Addario-Berry, Louigi; Chudnovsky, Maria; Havet, Frédéric; Reed, Bruce; Seymour, Paul (2008), "Bisimplicial vertices in even-hole-free graphs", Journal of Combinatorial Theory , Series B, 98 (6): 1119–1164, doi:10.1016/j.jctb.2007.12.006
4. Chudnovsky, Maria; Seymour, Paul (2023), "Even-hole-free graphs still have bisimplicial vertices", Journal of Combinatorial Theory, Series B, 161: 331–381, arXiv: 1909.10967 , doi:10.1016/j.jctb.2023.02.009