Concept
Perfect graph
Related concepts (60)
Rook's graph
In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape.
Clique cover
In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum k for which a clique cover exists is called the clique cover number of the given graph. A clique cover of a graph G may be seen as a graph coloring of the complement graph of G, the graph on the same vertex set that has edges between non-adjacent vertices of G.
Windmill graph
In the mathematical field of graph theory, the windmill graph Wd(k,n) is an undirected graph constructed for k ≥ 2 and n ≥ 2 by joining n copies of the complete graph K_k at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs. It has n(k – 1) + 1 vertices and nk(k − 1)/2 edges, girth 3 (if k > 2), radius 1 and diameter 2. It has vertex connectivity 1 because its central vertex is an articulation point; however, like the complete graphs from which it is formed, it is (k – 1)-edge-connected.
Lovász number
In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by , using a script form of the Greek letter theta to contrast with the upright theta used for Shannon capacity. This quantity was first introduced by László Lovász in his 1979 paper On the Shannon Capacity of a Graph. Accurate numerical approximations to this number can be computed in polynomial time by semidefinite programming and the ellipsoid method.
K-tree
In graph theory, a k-tree is an undirected graph formed by starting with a (k + 1)-vertex complete graph and then repeatedly adding vertices in such a way that each added vertex v has exactly k neighbors U such that, together, the k + 1 vertices formed by v and U form a clique. The k-trees are exactly the maximal graphs with a treewidth of k ("maximal" means that no more edges can be added without increasing their treewidth).
Parity graph
In graph theory, a parity graph is a graph in which every two induced paths between the same two vertices have the same parity: either both paths have odd length, or both have even length. This class of graphs was named and first studied by . Parity graphs include the distance-hereditary graphs, in which every two induced paths between the same two vertices have the same length.
Modular graph
In graph theory, a branch of mathematics, the modular graphs are undirected graphs in which every three vertices x, y, and z have at least one median vertex m(x, y, z) that belongs to shortest paths between each pair of x, y, and z. Their name comes from the fact that a finite lattice is a modular lattice if and only if its Hasse diagram is a modular graph. It is not possible for a modular graph to contain a cycle of odd length. For, if C is a shortest odd cycle in a graph, x is a vertex of C, and yz is the edge of C farthest from x, there could be no median m(x, y, z).
Line perfect graph
In graph theory, a line perfect graph is a graph whose line graph is a perfect graph. Equivalently, these are the graphs in which every odd-length simple cycle is a triangle. A graph is line perfect if and only if each of its biconnected components is a bipartite graph, the complete graph K_4, or a triangular book K_1,1,n. Because these three types of biconnected component are all perfect graphs themselves, every line perfect graph is itself perfect.
Disjoint union of graphs
In graph theory, a branch of mathematics, the disjoint union of graphs is an operation that combines two or more graphs to form a larger graph. It is analogous to the disjoint union of sets, and is constructed by making the vertex set of the result be the disjoint union of the vertex sets of the given graphs, and by making the edge set of the result be the disjoint union of the edge sets of the given graphs. Any disjoint union of two or more nonempty graphs is necessarily disconnected.
Biconnected component
In graph theory, a biconnected component (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components.