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:
“Becoming responsible adults is no longer a matter of whether children hang up their pajamas or put dirty towels in the hamper, but whether they care about themselves and others—and whether they see everyday chores as related to how we treat this planet.”
—Eda Le Shan (20th century)
“Science is a dynamic undertaking directed to lowering the degree of the empiricism involved in solving problems; or, if you prefer, science is a process of fabricating a web of interconnected concepts and conceptual schemes arising from experiments and observations and fruitful of further experiments and observations.”
—James Conant (1893–1978)