Generalizations and Related Concepts
A graph is said to be k-factor-critical if every subset of n − k vertices has a perfect matching. Under this definition, a hypomatchable graph is 1-factor-critical. Even more generally, a graph is (a,b)-factor-critical if every subset of n − k vertices has an r-factor, that is, it is the vertex set of an r-regular subgraph of the given graph.
A critical graph (without qualification) is usually assumed to mean a graph for which removing each of its vertices reduces the number of colors it needs in a graph coloring. The concept of criticality has been used much more generally in graph theory to refer to graphs for which removing each possible vertex changes or does not change some relevant property of the graph. A matching-critical graph is a graph for which the removal of any vertex does not change the size of a maximum matching; by Gallai's characterization, the matching-critical graphs are exactly the graphs in which every connected component is factor-critical. The complement graph of a critical graph is necessarily matching-critical, a fact that was used by Gallai to prove lower bounds on the number of vertices in a critical graph.
Beyond graph theory, the concept of factor-criticality has been extended to matroids by defining a type of ear decomposition on matroids and defining a matroid to be factor-critical if it has an ear decomposition in which all ears are odd.
Read more about this topic: Factor-critical Graph
Famous quotes containing the words related and/or concepts:
“So universal and widely related is any transcendent moral greatness, and so nearly identical with greatness everywhere and in every age,—as a pyramid contracts the nearer you approach its apex,—that, when I look over my commonplace-book of poetry, I find that the best of it is oftenest applicable, in part or wholly, to the case of Captain Brown.”
—Henry David Thoreau (1817–1862)
“Institutional psychiatry is a continuation of the Inquisition. All that has really changed is the vocabulary and the social style. The vocabulary conforms to the intellectual expectations of our age: it is a pseudo-medical jargon that parodies the concepts of science. The social style conforms to the political expectations of our age: it is a pseudo-liberal social movement that parodies the ideals of freedom and rationality.”
—Thomas Szasz (b. 1920)