Maximal clique

Mathematics

• A cluster graph is a graph whose connected components are cliques.
• A block graph is a graph whose biconnected components are cliques.
• A chordal graph is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the neighbors of each vertex v that come later than v in the ordering form a clique.
• A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
• An interval graph is a graph whose maximal cliques can be ordered in such a way that, for each vertex v, the cliques containing v are consecutive in the ordering.
• A line graph is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover.
• A perfect graph is a graph in which the clique number equals the chromatic number in every induced subgraph.
• A split graph is a graph in which some clique contains at least one endpoint of every edge.
• A triangle-free graph is a graph that has no cliques other than its vertices and edges.