Simplicial vertex

File:Bisimplicial vertex.svg (denoted in black).]]

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

| last1 = Agnarsson

| first1 = Geir

| last2 = Halldórsson

| first2 = Magnús M.

| title = Strongly simplicial vertices of powers of trees

| journal = Discrete Mathematics

| volume = 307

| issue = 21

| pages = 2647–2652

| date = October 2007

| doi = 10.1016/j.disc.2007.01.002

| doi-access = free

}}

A vertex of a graph is bisimplicial if the set of it and its neighbours is the union of two cliques, and is {{mvar|k}}-simplicial if the set is the union of {{mvar|k}} cliques. A vertex is co-simplicial if its non-neighbours form an independent set.{{cite journal

| last1 = Hoàng

| first1 = Chính T.

| last2 = Hougardy

| first2 = Stefan

| last3 = Maffray

| first3 = Frédéric

| last4 = Mahadev

| first4 = N. V. R.

| title = On simplicial and co-simplicial vertices in graphs

| journal = Discrete Applied Mathematics

| volume = 138

| issue = 1–2

| pages = 117–132

| date = 29 March 2004

| doi = 10.1016/S0166-218X(03)00275-0

}}

Addario-Berry et al.{{citation

| last1 = Addario-Berry | first1 = Louigi

| last2 = Chudnovsky | first2 = Maria | author2-link = Maria Chudnovsky

| last3 = Havet | first3 = Frédéric

| last4 = Reed | first4 = Bruce | author4-link = Bruce Reed (mathematician)

| last5 = Seymour | first5 = Paul | author5-link = Paul Seymour (mathematician)

| title = Bisimplicial vertices in even-hole-free graphs

| journal = Journal of Combinatorial Theory | series=Series B

| volume = 98 | issue = 6 | year = 2008 | pages = 1119–1164

| doi = 10.1016/j.jctb.2007.12.006| doi-access = }} 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,{{citation

| title = Even-hole-free graphs still have bisimplicial vertices

| last1 = Chudnovsky | first1 = Maria

| last2 = Seymour | first2 = Paul

| journal = Journal of Combinatorial Theory, Series B

| year = 2023

| volume = 161 | pages = 331–381 | doi = 10.1016/j.jctb.2023.02.009

| url = https://www.sciencedirect.com/science/article/pii/S0095895623000151

| arxiv = 1909.10967

}} who gave a correct proof. Due to this property, the family of all even-cycle-free graphs is $\backslash chi$-bounded.