graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a simplicial vertex

v

is a vertex whose closed neighborhood

N_/math> in a graph G forms a

clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

, where every pair of neighbors is adjacent to each other. A vertex of a graph is bisimplicial if the set of it and its neighbours is the union of two cliques, and is -simplicial if the set is the union of cliques. A vertex is co-simplicial if its non-neighbours form an independent set. Addario-Berry et al. 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, who gave a correct proof. Due to this property, the family of all even-cycle-free graphs is

\chi

-bounded.

References

{{graph-stub Graph theory

See also

References