8 citations · 27 across the 16 of their papers we have counts for
17 papers
Odd Cuts in Bipartite Grafts II: Structure and Universality of Decapital Distance Components
Nanao Kita
This paper is the second in a series of papers characterizing the maximum packing of \( T \)-cuts in bipartite grafts, following the first paper (N.~Kita, ``Tight cuts in bipartite…
Constructive Characterization for Signed Analogue of Critical Graphs II: General Radials and Semiradials
Nanao Kita
This paper is a sequel of our preceding paper (N. Kita: Constructive characterization for signed analogue of critical graphs I: Principal classes of radials and semiradials. arXiv…
Tight Cuts in Bipartite Grafts I: Capital Distance Components
Nanao Kita
This paper is the first from a series of papers that provide a characterization of maximum packings of -cuts in bipartite graphs. Given a connected graph, a set of an even n…
Bipartite Graft III: General Case
Nanao Kita
This paper is a sequel of our previous paper (N. Kita: Bipartite graft {II}: Cathedral decomposition for combs. arXiv preprint arXiv:2101.06678, 2021). In our previous paper, a gra…
Constructive Characterization of Critical Bipartite Grafts
Nanao Kita
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 ma…
Bipartite Graft II: Cathedral Decomposition for Combs
Nanao Kita
We provide a canonical decomposition for a class of bipartite grafts known as combs. As every bipartite graft is a recursive combination of combs, our results provides a canonical…
Bipartite Graft I: Dulmage-Mendelsohn Decomposition for Combs
Nanao Kita
We provide an analogue of the Dulmage-Mendelsohn decomposition for a class of grafts known as comb-bipartite grafts. The Dulmage-Mendelsohn decomposition in matching theory is a cl…
Constructive Characterization for Bidirected Analogue of Critical Graphs I: Principal Classes of Radials and Semiradials
Nanao Kita
This paper is the first from serial papers that provide constructive characterizations for classes of bidirected graphs known as radials and semiradials. In this paper, we provide…
Parity Factors I: General Kotzig-Lovász Decomposition for Grafts
Nanao Kita
This paper is the first from a series of papers that establish a generalization of the basilica decomposition for cardinality minimum joins in grafts. Joins in grafts are also know…
Bidirected Graphs I: Signed General Kotzig-Lovász Decomposition
Nanao Kita
This paper is the first from a series of papers that establish a common analogue of the strong component and basilica decompositions for bidirected graphs. A bidirected graph is a…
New Canonical Decomposition in Matching Theory
Nanao Kita
In matching theory, one of the most fundamental and classical branches of combinatorics, {\em canonical decompositions} of graphs are powerful and versatile tools that form the bas…
Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality
Nanao Kita
The Dulmage-Mendelsohn decomposition is a classical canonical decomposition in matching theory applicable for bipartite graphs, and is famous not only for its application in the fi…
The Dulmage-Mendelsohn Decomposition for -Matchings
Nanao Kita
We establish the theory of the Dulmage-Mendelsohn decomposition for -matchings. The original Dulmage-Mendelsohn decomposition is a classical canonical decomposition of bipartite…
A Graph Theoretic Proof of the Tight Cut Lemma
Nanao Kita
In deriving their characterization of the perfect matchings polytope, Edmonds, Lovász, and Pulleyblank introduced the so-called {\em Tight Cut Lemma} as the most challenging aspect…
The Third Proof of Lovász's Cathedral Theorem
Nanao Kita
A graph with a perfect matching is called saturated if has more perfect matchings than for any edge that is not in . Lovász gave a characterization of the satu…
A Canonical Characterization of the Family of Barriers in General Graphs
Nanao Kita
Given a graph, a barrier is a set of vertices determined by the Berge formula---the min-max theorem characterizing the size of maximum matchings. The notion of barriers plays impor…
A Partially Ordered Structure and a Generalization of the Canonical Partition for General Graphs with Perfect Matchings
Nanao Kita
This paper is concerned with structures of general graphs with perfect matchings. We first reveal a partially ordered structure among factor-components of general graphs with perfe…