Critical graph

Quality 0.50 · 3 views · Updated 2 months ago

Undirected graph

title: "Critical graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families", "graph-coloring"] description: "Undirected graph" topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Critical_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Undirected graph ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/a/a8/Critical_graph_sample.svg" caption="On the left-top a vertex critical graph with chromatic number 6; next all the N-1 subgraphs with chromatic number 5."] ::

In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. Each time a single edge or vertex (along with its incident edges) is removed from a critical graph, the decrease in the number of colors needed to color that graph cannot be by more than one.

Variations

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:

  • G has only one component.
  • G is finite (this is the De Bruijn–Erdős theorem).
  • The minimum degree \delta(G) obeys the inequality \delta(G)\ge k-1. That is, every vertex is adjacent to at least k-1 others. More strongly, G is (k-1)-edge-connected.
  • If G is a regular graph with degree k-1, meaning every vertex is adjacent to exactly k-1 others, then G is either the complete graph K_k with n=k vertices, or an odd-length cycle graph. This is Brooks' theorem.
  • 2m\ge(k-1)n+k-3.
  • 2m\ge (k-1)n+(k-3)/(k^2-3)n.
  • Either G may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or G has at least 2k-1 vertices. More strongly, either G has a decomposition of this type, or for every vertex v of G there is a k-coloring in which v is the only vertex of its color and every other color class has at least two vertices.

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 showed, every k-critical graph may be formed from a complete graph K_k 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. It is an open problem to determine whether K_k is the only double-critical k-chromatic graph.

References

References

  1. (1941). "On colouring the nodes of a network". Proceedings of the Cambridge Philosophical Society.
  2. (1951). "A colour problem for infinite graphs and a problem in the theory of relations". Nederl. Akad. Wetensch. Proc. Ser. A.
  3. Dirac, G. A.. (1957). "A theorem of R. L. Brooks and a conjecture of H. Hadwiger". Proceedings of the London Mathematical Society.
  4. Erdős, Paul. (1967). "In Theory of Graphs". Proc. Colloq., Tihany.
  5. Gallai, T.. (1963). "Kritische Graphen I". Publ. Math. Inst. Hungar. Acad. Sci..
  6. Gallai, T.. (1963). "Kritische Graphen II". Publ. Math. Inst. Hungar. Acad. Sci..
  7. Hajós, G.. (1961}} <!-- Might be in: Bericht 1951-1966: Gesamtregister der Jahrgänge I-XV: Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg. Germany: n.p., 1969. {{GBurl). "Über eine Konstruktion nicht {{mvar". Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe.
  8. Lovász, László. (1992). "Combinatorial Problems and Exercises". North-Holland.
  9. Stehlík, Matěj. (2003). "Critical graphs with connected complements". [[Journal of Combinatorial Theory]].

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

graph-familiesgraph-coloring