TOPICS
Search

Edge-Critical Graph

An edge-critical graph is a graph for which deleting any graph edge lowers the chromatic number. More specifically, a graph G is k-edge-critical if its chromatic number is k and chi(G-e)=k-1 for every edge e (Jensen and Toft 1995, Chiu et al. 2024).

The complete graph K_k is k-edge-critical, while the cycle graph C_(2n+1) is 3-edge-critical. The Chiu graph is a 4-edge-critical quartic graph and a planar graph.

See also

Chromatic Number, Complete Graph, Cycle Graph, Edge Deletion, Vertex-Critical Graph

Explore with Wolfram|Alpha

References

Chiu, M.-K.; Felsner, S.; Scheucher, M.; Schröder, F.; Steiner, R.; and Vogtenhuber, B. "Coloring Circle Arrangements: New 4-Chromatic Planar Graphs." European J. Combin. 121, 103839, 2024. https://doi.org/10.1016/j.ejc.2023.103839.Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1995.

Cite this as:

Weisstein, Eric W. "Edge-Critical Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Edge-CriticalGraph.html

Subject classifications