Recognizing near-bipartite Pfaffian graphs in polynomial time

A matching covered graph is a non-trivial connected graph in which every edge is in some perfect matching. A non-bipartite matching covered graph G is near-bipartite if there are two edges e₁ and e₂ such that G−e₁−e₂ is bipartite and matching covered. In 2000, Fischer and Little characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [I. Fischer, C.H.C. Little, A characterization of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001) 175-222.]. However, their characterization does not imply a polynomial time algorithm to recognize near-bipartite Pfaffian graphs. In this article, we give such an algorithm.We define a more general class of matching covered graphs, which we call weakly near-bipartite graphs. This class includes the near-bipartite graphs. We give a polynomial algorithm for recognizing weakly near-bipartite Pfaffian graphs. We also show that Fischer and Little’s characterization of near-bipartite Pfaffian graphs extends to this wider class.     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Graph theoretic approach to parallel gene assembly

We study parallel complexity of signed graphs motivated by the highly complex genetic recombination processes in ciliates. The molecular gene assembly operations have been modeled by operations of signed graphs, i.e., graphs where the vertices have a sign + or −. In the optimization problem for signed graphs one wishes to find the parallel complexity by which the graphs can be reduced to the empty graph. We relate parallel complexity to matchings in graphs for some natural graph classes, especially bipartite graphs. It is shown, for instance, that a bipartite graph G has parallel complexity one if and only if G has a unique perfect matching. We also formulate some open problems of this research topic.     

Minimally non-Pfaffian graphs

We consider the question of characterizing Pfaffian graphs. We exhibit an infinite family of non-Pfaffian graphs minimal with respect to the matching minor relation. This is in sharp contrast with the bipartite case, as Little [C.H.C. Little, A characterization of convertible (0,1)-matrices, J. Combin. Theory Ser. B 18 (1975) 187–208] proved that every bipartite non-Pfaffian graph contains a matching minor isomorphic to K_3,3. We relax the notion of a matching minor and conjecture that there are only finitely many (perhaps as few as two) non-Pfaffian graphs minimal with respect to this notion.We define Pfaffian factor-critical graphs and study them in the second part of the paper. They seem to be of interest as the number of near perfect matchings in a Pfaffian factor-critical graph can be computed in polynomial time. We give a polynomial time recognition algorithm for this class of graphs and characterize non-Pfaffian factor-critical graphs in terms of forbidden central subgraphs.     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

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     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

Coloring quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory     

A perfect matching algorithm for sparse bipartite graphs

This paper considers an algorithm for finding a perfect matching, if there is one, in a bipartite graph G. It is shown that the search for a perfect matching in G may be carried on separately in the strongly connected components of appropriate directed graphs. The algorithm may be particularly useful for block triangularization of very large, sparse, nonsingular matrices.     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Algebraic Shifting of Finite Graphs

In the present article, for bipartite graphs and chordal graphs, their exterior algebraic shifted graph and their symmetric algebraic shifted graph are studied. First, we will determine the symmetric algebraic shifted graph of complete bipartite graphs. It turns out that for a ≥ 3 and b ≥ 3, the exterior algebraic shifted graph of the complete bipartite graph K _a,b of size a, b is different from the symmetric algebraic shifted graph of K _a,b . Second, we will show that the exterior algebraic shifted graph of any chordal graph G coincides with the symmetric algebraic shifted graph of G. In addition, it will be shown that the exterior algebraic shifted graph of any chordal graph G is equal to some combinatorial shifted graph of G.     

Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

On forcing matching number of boron-nitrogen fullerene graphs

Let G be a graph that admits a perfect matching M. A forcing set S for a perfect matching M is a subset of M such that it is contained in no other perfect matchings of G. The smallest cardinality of forcing sets of M is called the forcing number of M. Computing the minimum forcing number of perfect matchings of a graph is an NP-complete problem. In this paper, we consider boron-nitrogen (BN) fullerene graphs, cubic 3-connected plane bipartite graphs with exactly six square faces and other hexagonal faces. We obtain the forcing spectrum of tubular BN-fullerene graphs with cyclic edge-connectivity 3. Then we show that all perfect matchings of any BN-fullerene graphs have the forcing number at least two. Furthermore, we mainly construct all seven BN-fullerene graphs with the minimum forcing number two.     

A characterization of well-covered graphs in terms of prohibited costable subgraphs

A graph is calledwell-covered if all maximal independent subsets in it have the same number of elements. LetI be an independent subset (possibly empty) in a graphG. The subgraph ofG obtained by erasing the setI together with its neighborhood is calledcostable. We present a characterization of the class of well-covered graphs in terms of the minimal set of prohibited costable subgraphs. This characterization implies characterizations of some well-known subclasses of the class of well-covered graphs as well as the existence of a polynomial algorithm for the recognition of well-covered graphs with bounded valences. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 52–56, January, 2000.     

Forcing faces in plane bipartite graphs

Let Ω denote the class of connected plane bipartite graphs with no pendant edges. A finite face s of a graph G∈Ω is said to be a forcing face of G if the subgraph of G obtained by deleting all vertices of s together with their incident edges has exactly one perfect matching. This is a natural generalization of the concept of forcing hexagons in a hexagonal system introduced in Che and Chen [Forcing hexagons in hexagonal systems, MATCH Commun. Math. Comput. Chem. 56 (3) (2006) 649-668]. We prove that any connected plane bipartite graph with a forcing face is elementary. We also show that for any integers n and k with n?4 and n?k?0, there exists a plane elementary bipartite graph such that exactly k of the n finite faces of G are forcing. We then give a shorter proof for a recent result that a connected cubic plane bipartite graph G has at least two disjoint M-resonant faces for any perfect matching M of G, which is a main theorem in the paper [S. Bau, M.A. Henning, Matching transformation graphs of cubic bipartite plane graphs, Discrete Math. 262 (2003) 27-36]. As a corollary, any connected cubic plane bipartite graph has no forcing faces. Using the tool of Z-transformation graphs developed by Zhang et al. [Z-transformation graphs of perfect matchings of hexagonal systems, Discrete Math. 72 (1988) 405-415; Plane elementary bipartite graphs, Discrete Appl. Math. 105 (2000) 291-311], we characterize the plane elementary bipartite graphs whose finite faces are all forcing. We also obtain a necessary and sufficient condition for a finite face in a plane elementary bipartite graph to be forcing, which enables us to investigate the relationship between the existence of a forcing edge and the existence of a forcing face in a plane elementary bipartite graph, and find out that the former implies the latter but not vice versa. Moreover, we characterize the plane bipartite graphs that can be turned to have all finite faces forcing by subdivisions.     

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     

On Unicyclic Graphs with Uniquely Restricted Maximum Matchings

A graph is called unicyclic if it owns only one cycle. A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. Clearly, μ _r (G) ≤ μ(G), where μ _r (G) denotes the size of a maximum uniquely restricted matching, while μ(G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μ _r (G) = μ(G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings.     

Minimum degree of minimal defect -extendable bipartite graphs

A near perfect matching is a matching saturating all but one vertex in a graph. If G is a connected graph and any n independent edges in G are contained in a near perfect matching, then G is said to be defect n-extendable. If for any edge e in a defect n-extendable graph G, G−e is not defect n-extendable, then G is minimal defect n-extendable. The minimum degree and the connectivity of a graph G are denoted by δ(G) and κ(G) respectively. In this paper, we study the minimum degree of minimal defect n-extendable bipartite graphs. We prove that a minimal defect 1-extendable bipartite graph G has δ(G)=1. Consider a minimal defect n-extendable bipartite graph G with n≥2, we show that if κ(G)=1, then δ(G)≤n+1 and if κ(G)≥2, then 2≤δ(G)=κ(G)≤n+1. In addition, graphs are also constructed showing that, in all cases but one, there exist graphs with minimum degree that satisfies the established bounds.     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009