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:
“The near explains the far. The drop is a small ocean. A man is related to all nature. This perception of the worth of the vulgar is fruitful in discoveries. Goethe, in this very thing the most modern of the moderns, has shown us, as none ever did, the genius of the ancients.”
—Ralph Waldo Emerson (1803–1882)
“During our twenties...we act toward the new adulthood the way sociologists tell us new waves of immigrants acted on becoming Americans: we adopt the host culture’s values in an exaggerated and rigid fashion until we can rethink them and make them our own. Our idea of what adults are and what we’re supposed to be is composed of outdated childhood concepts brought forward.”
—Roger Gould (20th century)