On the polyhedral lift-and-project methods and the fractional stable set polytope

We study two polyhedral lift-and-project operators (originally proposed by Lovász and Schrijver in 1991) applied to the fractional stable set polytopes. First, we provide characterizations of all valid inequalities generated by these operators. Then, we present some seven-node graphs on which the operator enforcing the symmetry of the matrix variable is strictly stronger on the odd-cycle polytope of these graphs than the operator without this symmetry requirement. This disproves a conjecture of Lipták and Tunçel from 2003.     

The bandwidth problem for graphs and matrices—a survey

The bandwidth problem for a graph G is to label its n vertices v_i with distinct integers f(v_i) so that the quantity max{| f(v_i) ? f(v_i)| : (v_i v_j) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i ? j| : m'_ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.     

Laplace eigenvalues and bandwidth-type invariants of graphs

For (weighted) graphs several labeling properties and their relation to the eigenvalues of the Laplacian matrix of a graph are considered. Several upper and lower bounds on the bandwidth and other min-sum problems are derived. Most of these bounds depend on Laplace eigenvalues of the graphs. The results are applied in the study of bandwidth and the min-sums of random graphs, random regular graphs, and Kneser graphs. © John Wiley & Sons, Inc.     

A bandwidth reduction algorithm for L-shaped and Z-shaped grid structured graphs

In this paper, a viable bandwidth reduction algorithm based on graphs for reducing the bandwidth of sparse symmetric matrices, arising from standard L-structured and Z-structured graphs, is presented. Bandwidth results for these matrices are obtained using this algorithm and compared with that of existing algorithms. This algorithm can easily be applied to these matrices while the bandwidths obtained are as good as those obtained with the existing algorithms.     

On the Structure of Bull-Free Perfect Graphs, 2: the Weakly Chordal Case

 A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. A graph is perfectly orderable if it admits an ordering such that the greedy sequential method applied on this ordering produces an optimal coloring for every induced subgraph. Chvátal conjectured that every bull-free graph with no odd hole or antihole is perfectly orderable. In a previous paper we studied the structure of general bull-free perfect graphs, and reduced Chvátal's conjecture to the case of weakly chordal graphs. Here we focus on weakly chordal graphs, and we reduce Chvátal's conjecture to a restricted case. Our method lays out the structure of all bull-free weakly chordal graphs. These results have been used recently by Hayward to establish Chvátal's conjecture for this restricted case and therefore in full. Received: November 26, 1997?Final version received: February 27, 2001     

Locally finite graphs with ends: A topological approach, II. Applications

This paper is the second of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [20]. They are complemented by a third part [31], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. This second part of the survey concentrates on these applications, many of which solve problems or extend earlier work of Thomassen on infinite graphs. Numerous new problems are suggested.     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

Some classes of perfectly orderable graphs

In 1981, Chvátal defined the class of perfectly orderable graphs. This class of perfect graphs contains the comparability graphs and the triangulated graphs. In this paper, we introduce four classes of perfectly orderable graphs, including natural generalizations of the comparability and triangulated graphs. We provide recognition algorithms for these four classes. We also discuss how to solve the clique, clique cover, coloring, and stable set problems for these classes.     

From graphs to ortholattices and equivariant maps

A functor is constructed from the category of graphs and graph homomorphisms to the category of spaces with involutions and equivariant homotopy classes of maps. This can sometimes be used to prove lower bounds on chromatic numbers, and was inspired by Lovász's proof of Kneser's conjecture. Ortholattices occur as an intermediate step between graphs and spaces, and the correspondence between graphs and ortholattices is analyzed.     

On splittable colorings of graphs and hypergraphs

The notion of a split coloring of a complete graph was introduced by Erd?s and Gyárfás [ 7 ] as a generalization of split graphs. In this work, we offer an alternate interpretation by comparing such a coloring to the classical Ramsey coloring problem via a two‐round game played against an adversary. We show that the techniques used and bounds obtained on the extremal (r,m)‐split coloring problem of [ 7 ] are closer in nature to the Turán theory of graphs rather than Ramsey theory. We extend the notion of these colorings to hypergraphs and provide bounds and some exact results. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 226–237, 2002     

Sparse graphs: Metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with n vertices and Θ(n) edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function κ: [0, 1]² → [0, ∞). To understand these models, we should like to know when different kernels κ give rise to “similar” graphs, and, given a real‐world network, how “similar” is it to a typical graph G(n, κ) derived from a given kernel κ. The analogous questions for dense graphs, with Θ(n²) edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in [0, 1]. Possible generalizations of these results to graphs with o(n²) but ω(n) edges are discussed in a companion article [Bollobás and Riordan, London Math Soc Lecture Note Series 365 (2009), 211–287]; here we focus only on graphs with Θ(n) edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models and vice versa. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 1‐38, 2011     

Intersection graphs of subgroups of finite groups

In this paper we classify finite groups with disconnected intersection graphs of subgroups. This solves a problem posed by Csákány and Pollák.     

Proof of Ding’s conjecture on maximal stable sets and maximal cliques in planar graphs

X. Deng et al. proved Chvātal＇s conjecture on maximal stable sets and maximal cliques in graphs. G. Ding made a conjecture to generalize Chvátal＇s conjecture. The purpose of this paper is to prove this conjecture in planar graphs and the complement of planar graphs.     

Arc reversal in nonhamiltonian circulant oriented graphs

Locke and Witte described infinite families of nonhamiltonian circulant oriented graphs. We show that for infinitely many of them the reversal of any arc produces a hamiltonian cycle. This solves an open problem stated by Thomassen in 1987. We also use these graphs to construct counterexamples to Ádám's conjecture on arc reversal. One of them is a counterexample with the smallest known number of vertices. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 59–68, 2005     

Constructive proof of deficiency theorem of (g, f)-factor

Berge (1958) gave a formula for computing the deficiency of maximum matchings of a graph. More generally, Lovász obtained a deficiency formula of (g, f)-optimal graphs and consequently a criterion for the existence of (g, f)-factors. Moreover, Lovász proved that there is one of these decompositions which is “canonical“ in a sense. In this paper, we present a short constructive proof for the deficiency formula of (g, f)-optimal graphs, and the proof implies an efficient algorithm of time complexity O(g(V)|E|) for computing the deficiency. Furthermore, this proof implies this canonical decomposition via efficient algorithms (i.e., in polynomial time).     

A semi-strong Perfect Graph theorem

Perfect Graphs were defined by Claude Berge in 1961. Since that time this class of graphs has been intensely studied. Much of the work has been directed towards proving Berge's Strong and Weak Perfect Graph Conjectures. L. Lovász finally demonstrated the Weak Perfect Graph Conjecture in 1972. Vaśek Chvátal, in 1982, proposed the Semi-Strong Perfect Graph Conjecture which falls between these two conjectures. This conjecture suggests that the perfection of a graph depends solely on the way that the chordless paths with three edges are distributed within the graph. This paper contains a proof of Chvátal's conjecture.     

关于乘积图的二维带宽问题

给出一般乘积图的二维带宽的界，并解决一类乘积图的二维带宽问题．最后给出完全ｋ部图的二维带宽。     

Forbidden subgraphs and the König–Egerváry property

The matching number of a graph is the maximum size of a set of vertex-disjoint edges. The transversal number is the minimum number of vertices needed to meet every edge. A graph has the König–Egerváry property  if its matching number equals its transversal number. Lovász proved a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs within graphs with a perfect matching. Korach, Nguyen, and Peis proposed an extension of Lovász’s result to a characterization of all graphs having the König–Egerváry property in terms of forbidden configurations (which are certain arrangements of a subgraph and a maximum matching). In this work, we prove a characterization of graphs having the König–Egerváry property by means of forbidden subgraphs which is a strengthened version of the characterization by Korach et al. Using our characterization of graphs with the König–Egerváry property, we also prove a forbidden subgraph characterization for the class of edge-perfect graphs.