On perfect matchings in matching covered graphs

A graph is matching-covered if every edge of is contained in a perfect matching. A matching-covered graph is strongly coverable if, for any edge of , the subgraph is still matching-covered. An edge subset of a matching-covered graph is feasible if there exist two perfect matchings and such that , and an edge subset with at least two edges is an equivalent set if a perfect matching of contains either all edges in or none of them. A strongly matchable graph does not have an equivalent set, and any two independent edges of form a feasible set. In this paper, we show that for every integer , there exist infinitely many -regular graphs of class 1 with an arbitrarily large equivalent set that is not switching-equivalent to either or , which provides a negative answer to a problem of Lukot’ka and Rollová. For a matching-covered bipartite graph , we show that has an equivalent set if and only if it has a 2-edge-cut that separates into two balanced subgraphs, and is strongly coverable if and only if every edge-cut separating into two balanced subgraphs and satisfies and .     

Circular perfect graphs

For 1 ≤ d ≤ k, let K_k/d be the graph with vertices 0, 1, …, k ? 1, in which i ～j if d ≤ |i ? j| ≤ k ? d. The circular chromatic number χ_c(G) of a graph G is the minimum of those k/d for which G admits a homomorphism to K_k/d. The circular clique number ω_c(G) of G is the maximum of those k/d for which K_k/d admits a homomorphism to G. A graph G is circular perfect if for every induced subgraph H of G, we have χ_c(H) = ω_c(H). In this paper, we prove that if G is circular perfect then for every vertex x of G, N_G[x] is a perfect graph. Conversely, we prove that if for every vertex x of G, N_G[x] is a perfect graph and G ? N[x] is a bipartite graph with no induced P₅ (the path with five vertices), then G is a circular perfect graph. In a companion paper, we apply the main result of this paper to prove an analog of Haj?os theorem for circular chromatic number for k/d ≥ 3. Namely, we shall design a few graph operations and prove that for any k/d ≥ 3, starting from the graph K_k/d, one can construct all graphs of circular chromatic number at least k/d by repeatedly applying these graph operations. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 186–209, 2005     

On a conjecture of Hoàng and Tu concerning perfectly orderable graphs

Hoàng and Tu [On the perfect orderability of unions of two graphs, J. Graph Theory 33 (2000) 32-43] conjectured that a weakly triangulated graph which does not contain a chordless path with six vertices is perfectly orderable. We present a counter example to this conjecture.     

On critically perfect graphs

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, and study operations preserving critical perfectness. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 394–404, 1999     

Skew partitions in perfect graphs

We discuss some new and old results about skew partitions in perfect graphs.     

Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P_n sampled uniformly from the set of perfect graphs on vertex set . Our approach is based on the result of Prömel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number and clique number is close to a concentrated distribution L(n) which plays an important role in our generation method. We also prove that the probability that P_n contains any given graph H as an induced subgraph is asymptotically 0 or or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon .     

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     

Lift-and-project cuts and perfect graphs

We analyze the application of lift-and-project to the clique relaxation of the stable set polytope. We characterize all the inequalities that can be generated through the application of the lift-and-project procedure, introduce the concept of 1-perfection and prove its equivalence to minimal imperfection. This characterization of inequalities and minimal imperfection leads to a generalization of the Perfect Graph Theorem of Lovász, as proved by Aguilera, Escalante and Nasini [1].Mathematics Subject Classification:05C17, 90C57     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

Convex‐round graphs are circular‐perfect

We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal K_r‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002     

Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

Claw-free graphs with strongly perfect complements. Fractional and integral version. Part I. Basic graphs

Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement. We obtain a forbidden induced subgraph characterization and display graph-theoretic properties of such graphs. It turns out that the forbidden induced subgraphs that characterize claw-free graphs that are fractionally strongly perfect in the complement are precisely the cycle of length 6, all cycles of length at least 8, four particular graphs, and a collection of graphs that are constructed by taking two graphs, each a copy of one of three particular graphs, and joining them in a certain way by a path of arbitrary length. Wang (2006) [14] gave a characterization of strongly perfect claw-free graphs. As a corollary of the results in this paper, we obtain a characterization of claw-free graphs whose complements are strongly perfect.     

Neighborhood unions and cyclability of graphs

A graph G is said to be cyclable if for each orientation of G, there exists a set S of vertices such that reversing all the arcs of with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x₁, x₂ and x₃, |N(x₁)N(x₂)|+|N(x₂)N(x₃)|+|N(x₃)N(x₁)|2n+1, then G is cyclable.     

On factor-invariant graphs with two cycles

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a 2-factor composed of two cycles and a 1-factor that is invariant under the action of the automorphism group.     

Gk^d图的平面性和平面图的色数

利用欧拉公式研究了Gdk图的平面性,获得了一个重要定理,并由此得到了关于平面图色数的一个结论.     

Proof of a conjecture on irredundance perfect graphs

Let ir(G) and γ(G) be the irredundance number and the domination number of a graph G, respectively. A graph G is called irredundance perfect if ir(H)=γ(H), for every induced subgraph H of G. In this article we present a result which immediately implies three known conjectures on irredundance perfect graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 292–306, 2002     

Recursive generation of partitionable graphs

Results of Lovász (1972) and Padberg (1974) imply that partitionable graphs contain all the potential counterexamples to Berge's famous Strong Perfect Graph Conjecture. A recursive method of generating partitionable graphs was suggested by Chvátal, Graham, Perold, and Whitesides (1979). Results of Seb? (1996) entail that Berge's conjecture holds for all the partitionable graphs obtained by this method. Here we suggest a more general recursion. Computer experiments show that it generates all the partitionable graphs with ω=3,α ≤ 9 (and we conjecture that the same will hold for bigger α, too) and many but not all for (ω,α)=(4,4) and (4,5). Here, α and ω are respectively the clique and stability numbers of a partitionable graph, that is the numbers of vertices in its maximum cliques and stable sets. All the partitionable graphs generated by our method contain a critical ω‐clique, that is an ω‐clique which intersects only 2ω?2 other ω‐cliques. This property might imply that in our class there are no counterexamples to Berge's conjecture (cf. Seb? (1996)), however this question is still open. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 259–285, 2002