Definition
In graph theory, a critical graph is a graph that is minimal with respect to a given graph invariant, most commonly the chromatic number. A graph $G$ is k‑critical (or simply critical when the context is clear) if $\chi(G)=k$ and every proper subgraph $H\subsetneq G$ satisfies $\chi(H)<k$. Variants include vertex‑critical (removing any vertex reduces the chromatic number) and edge‑critical (removing any edge reduces the chromatic number).
Overview
Critical graphs arise in the study of graph coloring, particularly in the proofs of theorems concerning the chromatic number and the structure of minimally non‑$k$-colorable graphs. They serve as extremal examples: any graph with chromatic number $k$ contains a $k$-critical subgraph. Consequently, the class of critical graphs provides a foundation for inductive arguments and for establishing lower bounds on the size of graphs requiring many colors.
Historically, critical graphs were introduced in the early 20th century as part of investigations into the Four‑Color Problem and later formalized by mathematicians such as Dirac, Gallai, and others. The concept is central to several classic results, including Dirac’s theorem on the minimum degree of $k$-critical graphs and Gallai’s theorem relating the number of edges in a critical graph to its order.
Etymology / Origin
The adjective “critical” in this context derives from the notion of a critical point or critical threshold in mathematics—an element whose removal changes a key property. In graph theory, the term was first employed to describe graphs that are minimally non‑$k$-colorable, i.e., graphs that are “critical” for the property of requiring $k$ colors.
Characteristics
| Property | Description |
|---|---|
| Chromatic number | For a $k$-critical graph $G$, $\chi(G)=k$. |
| Minimality | Every proper subgraph $H$ of $G$ satisfies $\chi(H)<k$. This holds for vertex‑criticality (any vertex deletion) and edge‑criticality (any edge deletion). |
| Minimum degree | Dirac’s bound: a $k$-critical graph with $n$ vertices has minimum degree $\delta(G) \ge k-1$. |
| Edge count | Gallai’s inequality: for a $k$-critical graph, $ |
| Connectivity | Many $k$-critical graphs are (k‑1)-connected, though not all. |
| Examples | • Odd cycles $C_{2m+1}$ are 3‑critical. • Complete graphs $K_k$ are trivially $k$-critical. • The Grötzsch graph is 4‑critical and triangle‑free. |
| Construction | Critical graphs can be built via operations such as Mycielski’s construction, which yields $(k+1)$-critical graphs from $k$-critical ones while preserving triangle‑freeness. |
Related Topics
- Graph coloring – the broader study of assigning colors to vertices/edges under adjacency constraints.
- Chromatic number – the smallest number of colors needed for a proper vertex coloring.
- k‑critical graph – a specific instance of a critical graph with chromatic number $k$.
- Vertex‑critical / Edge‑critical graphs – variants focusing on removal of vertices or edges.
- Dirac’s theorem (critical graphs) – provides degree conditions for critical graphs.
- Gallai’s theorem (critical graphs) – gives lower bounds on edges in critical graphs.
- Mycielski’s construction – a method for generating triangle‑free critical graphs with increasing chromatic number.
- Perfect graphs – graphs in which the chromatic number equals the size of the largest clique for every induced subgraph; critical graphs are often studied in contrast to perfectness.
Critical graphs continue to be a focal point in extremal graph theory, algorithmic graph coloring, and the investigation of graph structure under coloring constraints.