2021年5月24日
Constructive Characterization of Critical Bipartite Grafts
Factor-critical graphs are a classical concept in matching theory that
constitute an important component of the Gallai-Edmonds canonical decomposition
and Edmonds' algorithm for maximum matchings. Lovász provided a constructive
characterization of factor-critical graphs in terms of ear decompositions. This
characterization has been a useful inductive tool for studying factor-critical
graphs and also connects them with Edmonds' algorithm.
Joins in grafts, also known as $T$-joins in graphs, are a classical variant
of matchings proposed in terms of parity. Minimum joins and grafts are
generalizations of perfect matchings and graphs with perfect matchings,
respectively. Accordingly, graft analogues of fundamental concepts and results
from matching theory, such as canonical decompositions, will develop the theory
of minimum join. In this paper, we propose a new concept, critical quasicombs,
as a bipartite graft analogue of factor-critical graphs and provide a
constructive characterization of critical quasicombs using a graft version of
ear decompositions. This characterization can be considered as a bipartite
graft analogue of Lovász' result. From our results, the Dulmage-Mendelsohn
canonical decomposition, originally a theory for bipartite graphs, has been
generalized for bipartite grafts.
constitute an important component of the Gallai-Edmonds canonical decomposition
and Edmonds' algorithm for maximum matchings. Lovász provided a constructive
characterization of factor-critical graphs in terms of ear decompositions. This
characterization has been a useful inductive tool for studying factor-critical
graphs and also connects them with Edmonds' algorithm.
Joins in grafts, also known as $T$-joins in graphs, are a classical variant
of matchings proposed in terms of parity. Minimum joins and grafts are
generalizations of perfect matchings and graphs with perfect matchings,
respectively. Accordingly, graft analogues of fundamental concepts and results
from matching theory, such as canonical decompositions, will develop the theory
of minimum join. In this paper, we propose a new concept, critical quasicombs,
as a bipartite graft analogue of factor-critical graphs and provide a
constructive characterization of critical quasicombs using a graft version of
ear decompositions. This characterization can be considered as a bipartite
graft analogue of Lovász' result. From our results, the Dulmage-Mendelsohn
canonical decomposition, originally a theory for bipartite graphs, has been
generalized for bipartite grafts.
- リンク情報
- ID情報
-
- arXiv ID : arXiv:2105.11167