Critical graph

In graph theory, a critical graph is a graph G in which every vertex or edge is a critical element, that is, if its deletion decreases the chromatic number of G. Such a decrease cannot be by more than 1. In graph theory, a critical graph is a graph G in which every vertex or edge is a critical element, that is, if its deletion decreases the chromatic number of G. Such a decrease cannot be by more than 1. A k-critical graph is a critical graph with chromatic number k; a graph G with chromatic number k is k-vertex-critical if each of its vertices is a critical element. Critical graphs are the minimal members in terms of chromatic number, which is a very important measure in graph theory. Some properties of a k-critical graph G with n vertices and m edges: Graph G is vertex-critical if and only if for every vertex v, there is an optimal proper coloring in which v is a singleton color class. As Hajós (1961) showed, every k-critical graph may be formed from a complete graph Kk by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require k colors in any proper coloring. A double-critical graph is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two. One open problem is to determine whether Kk is the only double-critical k-chromatic graph.