Matching graphs

The matching graph M(G) of a graph G is that graph whose vertices are the maximum matchings in G and where two vertices M₁ and M₂ of M(G) are adjacent if and only if |M₁ − M₂| = 1. When M(G) is connected, this graph models a metric space whose metric is defined on the set of maximum matchings in G. Which graphs are matching graphs of some graph is not known in general. We determine several forbidden induced subgraphs of matching graphs and add even cycles to the list of known matching graphs. In another direction, we study the behavior of sequences of iterated matching graphs. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 73–86, 1998     

Graphs isomorphic to their maximum matching graphs

The maximum matching graph M（G） of a graph G is a simple graph whose vertices are the maximum matchings of G and where two maximum matchings are adjacent in M（G） if they differ by exactly one edge. In this paper, we prove that if a graph is isomorphic to its maximum matching graph, then every block of the graph is an odd cycle.     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

Partial characterizations of clique-perfect and coordinated graphs: Superclasses of triangle-free graphs

A graph G is clique-perfect if the cardinality of a maximum clique-independent set of H equals the cardinality of a minimum clique-transversal of H, for every induced subgraph H of G. A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of clique-perfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem, W₄, bull}-free, both superclasses of triangle-free graphs.     

Partial characterizations of clique-perfect and coordinated graphs: superclasses of triangle-free graphs

A graph is clique-perfect if the cardinality of a maximum clique-independent set equals the cardinality of a minimum clique-transversal, for all its induced subgraphs. A graph G is coordinated if the chromatic number of the clique graph of H equals the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The complete lists of minimal forbidden induced subgraphs for the classes of cliqueperfect and coordinated graphs are not known, but some partial characterizations have been obtained. In this paper, we characterize clique-perfect and coordinated graphs by minimal forbidden induced subgraphs when the graph is either paw-free or {gem,W₄,bull}-free, two superclasses of triangle-free graphs.     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Matchings and spanning trees in Boolean weighted graphs

It is shown that in a 0-sum Boolean weighted graph G the sum of the weights taken over all the spanning trees equals the sum of the weights taken over all the perfect matchings in the graph G − v, where v is any vertex of G. Several related theorems are proved which include parity results on perfect matchings and spanning trees in Eulerian graphs. The ideas on perfect matchings in 0-sum Boolean weighted graphs are generalized to matchings in any Boolean weighted graph.     

Reduced graphs of diameter two

A graph H is collapsible if for every subset X ? V(H), H has a spanning connected subgraph whose set of odd-degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2-edge-connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.     

Rank of maximum matchings in a graph

The matching polytope is the convex hull of the incidence vectors of all (not necessarily perfect) matchings of a graphG. We consider here the problem of computing the dimension of the face of this polytope which contains the maximum cardinality matchings ofG and give a good characterization of this quantity, in terms of the cyclomatic number of the graph and families of odd subsets of the nodes which are always nearly perfectly matched by every maximum matching.This is equivalent to finding a maximum number of linearly independent representative vectors of maximum matchings ofG; the size of such a set is called thematching rank ofG. We also give in the last section a way of computing that rank independently of those parameters.Note that this gives us a good lower bound on the number of those matchings.     

Partitioning infinite trees

A graph G is bisectable if its edges can be colored by two colors so that the resulting monochromatic subgraphs are isomorphic. We show that any infinite tree of maximum degree Δ with infinitely many vertices of degree at least Δ −1 is bisectable as is any infinite tree of maximum degree Δ ≤ 4. Further, it is proved that every infinite tree T of finite maximum degree contains a finite subset E of its edges so that the graph T − E is bisectable. To measure how “far” a graph G is from being bisectable, we define c(G) to be the smallest number k > 1 so that there is a coloring of the edges of G by k colors with the property that any two monochromatic subgraphs are isomorphic. An upper bound on c(G), which is in a sense best possible, is presented. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 113–127, 2000     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

Upper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

Graphs with the balas—uhry property

We characterize graphs H with the following property: Let G be a graph and F be a subgraph of G such that (i) each component of F is isomorphic to H or K₂, (ii) the order of F is maximum, and (iii) the number of H-components in F is minimum subject to (ii). Then a maximum matching of F is also a maximum matching of G. This result is motivated by an analogous property of fractional matchings discovered independently by J. P. Uhry and E. Balas.     

Geodesic subgraphs

Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs K_n' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs.     

Partial characterizations of coordinated graphs: line graphs and complements of forests

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. Coordinated graphs are a subclass of perfect graphs. The list of minimal forbidden induced subgraphs for the class of coordinated graphs is not known. In this paper, we present a partial result in this direction, that is, we characterize coordinated graphs by minimal forbidden induced subgraphs when the graph is either a line graph, or the complement of a forest. F. Bonomo, F. Soulignac, and G. Sueiro’s research partially supported by UBACyT Grant X184 (Argentina), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil). The research of G. Durán is partially supported by FONDECyT Grant 1080286 and Millennium Science Institute “Complex Engineering Systems” (Chile), and CNPq under PROSUL project Proc. 490333/2004-4 (Brazil).     

A generalization of line graphs: (X,Y)-intersection graphs

Given a pair (X, Y) of fixed graphs X and Y, the (X, Y)-intersection graph of a graph G is a graph whose vertices correspond to distinct induced subgraphs of G that are isomorphic to Y, and where two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X. This generalizes the notion of line graphs, since the line graph of G is precisely the (K₁, K₂)-intersection graph of G. In this paper, we consider the forbidden induced subgraph characterization of (X, Y)-intersection graphs for various (X, Y) pairs; such consideration is motivated by the characterization of line graphs through forbidden induced subgraphs. For this purpose, we restrict our attention to hereditary pairs (a pair (X, Y) is hereditary if every induced subgraph of any (X, Y)-intersection graph is also an (X, Y)-intersection graph), since only for such pairs do (X, Y)-intersection graphs have forbidden induced subgraph characterizations. We show that for hereditary 2-pairs (a pair (X, Y) is a 2-pair if Y contains exactly two induced subgraphs isomorphic to X), the family of line graphs of multigraphs and the family of line graphs of bipartite graphs are the maximum and minimum elements, respectively, of the poset on all families of (X, Y)-intersection graphs ordered by set inclusion. We characterize 2-pairs for which the family of (X, Y)-intersection graphs are exactly the family of line graphs or the family of line graphs of multigraphs. © 1996 John Wiley & Sons, Inc.     

Covering 2‐paths uniformly

We survey the existence of designs which consist of a set of subgraphs H_i of a graph G that between them uniformly cover the 2‐paths of G, such that the H_i are all isomorphic to a given subgraph H of G. We also construct several new designs in this family. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 100–121, 2000     

Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids

A matching M is uniquely restricted in a graph G if its saturated vertices induce a subgraph which has a unique perfect matching, namely M itself [M.C. Golumbic, T. Hirst, M. Lewenstein, Uniquely restricted matchings, Algorithmica 31 (2001) 139-154]. G is a König-Egerváry graph provided α(G)+μ(G)=|V(G)| [R.W. Deming, Independence numbers of graphs—an extension of the König-Egerváry theorem, Discrete Math. 27 (1979) 23-33; F. Sterboul, A characterization of the graphs in which the transversal number equals the matching number, J. Combin. Theory Ser. B 27 (1979) 228-229], where μ(G) is the size of a maximum matching and α(G) is the cardinality of a maximum stable set. S is a local maximum stable set of G, and we write S∈Ψ(G), if S is a maximum stable set of the subgraph spanned by S∪N(S), where N(S) is the neighborhood of S. Nemhauser and Trotter [Vertex packings: structural properties and algorithms, Math. Programming 8 (1975) 232-248], proved that any S∈Ψ(G) is a subset of a maximum stable set of G. In [V.E. Levit, E. Mandrescu, Local maximum stable sets in bipartite graphs with uniquely restricted maximum matchings, Discrete Appl. Math. 132 (2003) 163-174] we have proved that for a bipartite graph G,Ψ(G) is a greedoid on its vertex set if and only if all its maximum matchings are uniquely restricted. In this paper we demonstrate that if G is a triangle-free graph, then Ψ(G) is a greedoid if and only if all its maximum matchings are uniquely restricted and for any S∈Ψ(G), the subgraph spanned by S∪N(S) is a König-Egerváry graph.     

On the chromatic spectrum of acyclic decompositions of graphs

If G is any graph, a G‐decomposition of a host graph H = (V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G‐decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G‐spectrum of H is the set of all chromatic indices taken on by G‐decompositions of H. If both S and T are trees, then the S‐spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S‐spectrum has two values, and if the host is allowed to be arbitrary, the S‐spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S‐spectrum of a general bipartite graph is NP‐hard. We show that if G has c > 1 components, then there is a host H whose G‐spectrum contains both 3 and 2c + 1. If G is a forest, then there is a tree T whose G‐spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007     

The size of strength-maximal graphs

Let G be a graph and let k′(G) be the edge-connectivity of G. The strength of G, denoted by k?′(G), is the maximum value of k′(H), where H runs over all subgraphs of G. A simple graph G is called k-maximal if k?′(G) ≤ k but for any edge e ∈ E(G^c), k?′(G + e) ≥ k + 1. Let G be a k-maximal graph of order n. In [3], Mader proved |E(G)| ≤ (n - k)k + (). In this note, we shall show (n - 1)k - () In?n/k + 2)? ≤ |E(G|, and characterize the extremal graphs. We shall also give a characterization of all k-maximal graphs.