On Perfect k-Matchings

In this paper, we generalize the notions of perfect matchings, perfect 2-matchings to perfect k-matchings and give a necessary and sufficient condition for the existence of perfect k-matchings. We show that a bipartite graph G contains a perfect k-matching if and only if it contains a perfect matching. Moreover, for regular graphs, we provide a sufficient condition for the existence of perfect k-matching in terms of the edge connectivity.     

A matching problem with side conditions

Given a graph G, a 2-matching is an assignment of nonnegative integers to the edges of G such that for each node i of G, the sum of the values on the edges incident with i is at most 2. A triangle-free 2-matching is a 2-matching such that no cycle of size 3 in G has the value 1 assigned to all of its edges. In this paper we describe explicity the convex hull of triangle-free 2-matchings by means of its extreme points and of its facets. We give a polynomially bounded algorithm which maximizes a linear function over the set of triangle-free 2-matchings. Finally we discuss some related problems.     

BIMATCHING DESIGNS

A collection of k-matchings of bipartite graph Kn1n with the property that every pair of independent edges lies in exactly λ of the k-matchings is called a BIMATCH(n, k, λ)-design. Existences and constructions for various BIMATCH (n, k, λ)-designs are given.     

Critical graphs,matchings and tours or a hierarchy of relaxations for the travelling salesman problem

A(perfect) 2-matching in a graphG=(V, E) is an assignment of an integer 0, 1 or 2 to each edge of the graph in such a way that the sum over the edges incident with each node is at most (exactly) two. The incidence vector of a Hamiltonian cycle, if one exists inG, is an example of a perfect 2-matching. Fork satisfying 1≦k≦|V|, we letP _k denote the problem of finding a perfect 2-matching ofG such that any cycle in the solution contains more thank edges. We call such a matching aperfect P _k -matching. Then fork<l, the problemP _k is a relaxation ofP ₁. Moreover if |V| is odd, thenP _1V1–2 is simply the problem of determining whether or notG is Hamiltonian. A graph isP _k -critical if it has no perfectP _k -matching but whenever any node is deleted the resulting graph does have one. Ifk=|V|, then a graphG=(V, E) isP _k -critical if and only if it ishypomatchable (the graph has an odd number of nodes and whatever node is deleted the resulting graph has a perfect matching). We prove the following results:

1. If a graph isP _k -critical, then it is alsoP _l -critical for all largerl. In particular, for allk, P _k -critical graphs are hypomatchable.
2. A graphG=(V, E) has a perfectP _k -matching if and only if for anyX?V the number ofP _k -critical components inG[V - X] is not greater than |X|.
3. The problemP _k can be solved in polynomial time provided we can recognizeP _k -critical graphs in polynomial time. In addition, we describe a procedure for recognizingP _k -critical graphs which is polynomial in the size of the graph and exponential ink.

     

Extremal double hexagonal chains with respect to k-matchings and k-independent sets

“Double hexagonal chains” can be considered as benzenoids constructed by successive fusions of successive naphthalenes along a zig-zag sequence of triples of edges as appear on opposite sides of each naphthalene unit. In this paper, we discuss the numbers of k-matchings and k-independent sets of double hexagonal chains, as well as Hosoya indices and Merrifield-Simmons indices, and obtain some extremal results: among all the double hexagonal chains with the same number of naphthalene units, (a) the double linear hexagonal chain has minimal k-matching number and maximal k-independent set number and (b) the double zig-zag hexagonal chain has maximal k-matching number and minimal k-independent set number, which are extensions to hexagonal chains [L. Zhang and F. Zhang, Extremal hexagonal chains concerning k-matchings and k-independent sets, J. Math. Chem. 27 (2000) 319-329].     

Finding odd cycle transversals

We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k.     

Edge-disjoint cycles in regular directed graphs

We prove that any k-regular directed graph with no parallel edges contains a collection of at least O(k²) edge-disjoint cycles; we conjecture that in fact any such graph contains a collection of at least (^k+1₂) disjoint cycles, and note that this holds for k ≤ 3. © 1996 John Wiley & Sons, Inc.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

The Erdős–Pósa Property for Odd Cycles in Graphs of Large Connectivity

Dedicated to the memory of Paul Erdős A graph G is k-linked if G has at least 2k vertices, and, for any vertices , , ..., , , , ..., , G contains k pairwise disjoint paths such that joins for i = 1, 2, ..., k. We say that G is k-parity-linked if G is k-linked and, in addition, the paths can be chosen such that the parities of their lengths are prescribed. We prove the existence of a function g(k) such that every g(k)-connected graph is k-parity-linked if the deletion of any set of less than 4k-3 vertices leaves a nonbipartite graph. As a consequence, we obtain a result of Erdős–Pósa type for odd cycles in graphs of large connectivity. Also, every -connected graph contains a totally odd -subdivision, that is, a subdivision of in which each edge of corresponds to an odd path, if and only if the deletion of any vertex leaves a nonbipartite graph. Received May 13, 1999/Revised June 19, 2000     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

Disjoint Hamilton cycles in the random geometric graph

We consider the standard random geometric graph process in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of edge‐length. For fixed k?1, weprove that the first edge in the process that creates a k‐connected graph coincides a.a.s. with the first edge that causes the graph to contain k/2 pairwise edge‐disjoint Hamilton cycles (for even k), or (k?1)/2 Hamilton cycles plus one perfect matching, all of them pairwise edge‐disjoint (for odd k). This proves and extends a conjecture of Krivelevich and M ler. In the special case when k = 2, our result says that the first edge that makes the random geometric graph Hamiltonian is a.a.s. exactly the same one that gives 2‐connectivity, which answers a question of Penrose. (This result appeared in three independent preprints, one of which was a precursor to this article.) We prove our results with lengths measured using the ?_p norm for any p>1, and we also extend our result to higher dimensions. © 2011 Wiley Periodicals, Inc. J Graph Theory 68:299‐322, 2011     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

Bicolored Matchings in Some Classes of Graphs

We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R|=n+1 such that perfect matchings with k red edges exist for all k,0≤k≤n. Given two integers p<q we also determine the minimum cardinality of a set R of red edges such that there are perfect matchings with p red edges and with q red edges. For 3-regular bipartite graphs, we show that if p≤4 there is a set R with |R|=p for which perfect matchings M_k exist with |M_k∩R|≤k for all k≤p. For trees we design a linear time algorithm to determine a minimum set R of red edges such that there exist maximum matchings with k red edges for the largest possible number of values of k.     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Integer flows

A k-flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6-flow that applies uniformly to each graph. The algorithm specializes to give a 5-flow for planar graphs.     

Fractional covers for forests and matchings

We give polynomial algorithms for the fractional covering problems for forests andb-matchings: min{1·y: yA≥w,y≥0} whereA is a matrix whose rows are the incidence vectors of forests/b-matchings respectively. It is shown that each problem can be solved by a series of max-flow/min-cut calculations, and hence the use of the ellipsoid algorithm to guarantee a polynomial algorithm can be avoided. Visiting professor at the European Institute for Advanced Studies in Management in Brussels and at CORE. Supported in part by the CIM. On leave from New York University, New York, NY 10006.     

Some geometric applications of Dilworth’s theorem

A geometric graph is a graph drawn in the plane such that its edges are closed line segments and no three vertices are collinear. We settle an old question of Avital, Hanani, Erdős, Kupitz, and Perles by showing that every geometric graph withn vertices andm>k ⁴ n edges containsk+1 pairwise disjoint edges. We also prove that, given a set of pointsV and a set of axis-parallel rectangles in the plane, then either there arek+1 rectangles such that no point ofV belongs to more than one of them, or we can find an at most 2·10⁵ k ⁸ element subset ofV meeting all rectangles. This improves a result of Ding, Seymour, and Winkler. Both proofs are based on Dilworth’s theorem on partially ordered sets. The research by János Pach was supported by Hungarian National Foundation for Scientific Research Grant OTKA-4269 and NSF Grant CCR-91-22103.