Perfect factorisations of bipartite graphs and Latin squares without proper subrectangles.
Perfect matching in general vs. cubic graphs : a note on the planar and bipartite cases
Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
It is known that finding a perfect matching in a general graph is AC0-equivalent to finding a perfect matching in a 3-regular (i.e. cubic) graph. In this paper we extend this result to both, planar and bipartite cases. In particular we prove that the construction problem for perfect matchings in planar graphs is as difficult as in the case of planar cubic graphs like it is known to be the case for the famous Map Four-Coloring problem. Moreover we prove that the existence and construction...
Perfect matching preservers.
Perfect matchings and -decomposability of increasing trees.
Perfect matchings for the three-term Gale-Robinson sequences.
Perfect Matchings in a Class of Bipartite Graphs
Perfect matchings in claw-free cubic graphs.
Perfect matchings in -regular graphs.
Perfect Set of Euler Tours of Kp,p,p
Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.
Perfect transversal in some graph products.
Perfectly balanced partitions of smoothed graphs.
Perfectly matchable subgraph problem on a bipartite graph
We consider the maximum weight perfectly matchable subgraph problem on a bipartite graph G=(UV,E) with respect to given nonnegative weights of its edges. We show that G has a perfect matching if and only if some vector indexed by the nodes in UV is a base of an extended polymatroid associated with a submodular function defined on the subsets of UV. The dual problem of the separation problem for the extended polymatroid is transformed to the special maximum flow problem on G. In this paper, we give...
Permanents, Pfaffian orientations, and even directed circuits.
Permutation separations and complete bipartite factorisations of .
Pfaffian orientation and enumeration of perfect matchings for some Cartesian products of graphs.
Placing bipartite graphs of small size II
In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.
Point partition numbers and generalized Nordhaus-Gaddum problems
Poisson matching
Suppose that red and blue points occur as independent homogeneous Poisson processes in ℝd. We investigate translation-invariant schemes for perfectly matching the red points to the blue points. For any such scheme in dimensions d=1, 2, the matching distance X from a typical point to its partner must have infinite d/2th moment, while in dimensions d≥3 there exist schemes where X has finite exponential moments. The Gale–Shapley stable marriage is one natural matching scheme, obtained by iteratively...
Polynomial-time partition of a graph into cliques.