Ear decompositions of join covered graphs

Join covered graphs are ±1-weighted graphs, without negative circuits, in which every edge lies in a zero-weight circuit. Join covered graphs are a natural generalization of matching covered graphs. Many important properties of matching covered graphs have been generalized to join covered graphs. In this paper, we generalize Lovász and Plummerʼs ear decomposition theorem of matching covered graphs to join covered graphs.     

On the Relation Between Two Minor-Monotone Graph Parameters

, where μ and λ are minor-monotone graph invariants introduced by Colin de Verdière [3] and van der Holst, Laurent, and Schrijver [5]. It is also shown that a graph G exists with . The graphs G with maximal planar complement and , characterised by Kotlov, Lovász, and Vempala, are shown to be forbidden minors for . Received: June 13, 1997     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

Copositive programming motivated bounds on the stability and the chromatic numbers

The Lovász theta number of a graph G can be viewed as a semidefinite programming relaxation of the stability number of G. It has recently been shown that a copositive strengthening of this semidefinite program in fact equals the stability number of G. We introduce a related strengthening of the Lovász theta number toward the chromatic number of G, which is shown to be equal to the fractional chromatic number of G. Solving copositive programs is NP-hard. This motivates the study of tractable approximations of the copositive cone. We investigate the Parrilo hierarchy to approximate this cone and provide computational simplifications for the approximation of the chromatic number of vertex transitive graphs. We provide some computational results indicating that the Lovász theta number can be strengthened significantly toward the fractional chromatic number of G on some Hamming graphs. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

Lovász and Schrijver (SIAM J. Optim. 1:166–190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796–817, 2001; Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293–303, 2001) and by de Klerk and Pasechnik (SIAM J. Optim. 12:875–892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in α(G) steps as it refines the hierarchy of Lovász and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after α(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.      

Semidefinite programming relaxations for graph coloring and maximal clique problems

The semidefinite programming formulation of the Lovász theta number does not only give one of the best polynomial simultaneous bounds on the chromatic number χ(G) or the clique number ω(G) of a graph, but also leads to heuristics for graph coloring and extracting large cliques. This semidefinite programming formulation can be tightened toward either χ(G) or ω(G) by adding several types of cutting planes. We explore several such strengthenings, and show that some of them can be computed with the same effort as the theta number. We also investigate computational simplifications for graphs with rich automorphism groups. Partial support by the EU project Algorithmic Discrete Optimization (ADONET), MRTN-CT-2003-504438, is gratefully acknowledged.     

Generalized Kneser coloring theorems with combinatorial proofs

The Kneser conjecture (1955) was proved by Lovász (1978) using the Borsuk-Ulam theorem; all subsequent proofs, extensions and generalizations also relied on Algebraic Topology results, namely the Borsuk-Ulam theorem and its extensions. Only in 2000, Matoušek provided the first combinatorial proof of the Kneser conjecture. Here we provide a hypergraph coloring theorem, with a combinatorial proof, which has as special cases the Kneser conjecture as well as its extensions and generalization by (hyper)graph coloring theorems of Dol’nikov, Alon-Frankl-Lovász, Sarkaria, and Kriz. We also give a combinatorial proof of Schrijver’s theorem. Oblatum 17-IV-2001 & 12-IX-2001?Published online: 19 November 2001 An erratum to this article is available at .     

Nonseparating cycles in K-Connected graphs

We show that every k-connected graph with no 3-cycle contains an edge whose contraction results in a k-connected graph and use this to prove that every (k + 3)-connected graph contains a cycle whose deletion results in a k-connected graph. This settles a problem of L. Lovász.     

Nearly bipartite graphs with large chromatic number

P. Erdős and A. Hajnal asked the following question. Does there exist a constant ε>0 with the following property: If every subgraphH of a graphG can be made bipartite by the omission of at most ε|H| edges where |H| denotes the number of vertices ofH thenx(H) ≦ 3. The aim of this note is to give a negative answer to this question and consider the analogous problem for hypergraphs. The first was done also by L. Lovász who used a different construction.     

Set Partition Complexes

The Hom complexes were introduced by Lovász to study topological obstructions to graph colorings. The vertices of Hom(G,K _n ) are the n-colorings of the graph G, and a graph coloring is a partition of the vertex set into independent sets. Replacing the independence condition with any hereditary condition defines a set partition complex. We show how coloring questions arising from, for example, Ramsey theory can be formulated with set partition complexes. It was conjectured by Babson and Kozlov, and proved by Čukić and Kozlov, that Hom(G,K _n ) is (n−d−2)-connected, where d is the maximal degree of a vertex of G. We generalize this to set partition complexes.     

Carathéodory-type Theorems à la Bárány

We generalise the famous Helly–Lovász theorem leading to a generalisation of the Bárány–Carathéodory theorem for oriented matroids in dimension ≤3. We also provide a non-metric proof of the latter colourful theorem for arbitrary dimensions and explore some generalisations in dimension 2.     

A lower bound on the number of removable ears of 1-extendable graphs

Let G be a 1-extendable graph distinct from K₂ and C_2n. A classical result of Lovász and Plummer (1986) [5, Theorem 5.4.6] states that G has a removable ear. Carvalho et al. (1999) [3] proved that G has at least Δ(G) edge-disjoint removable ears, where Δ(G) denotes the maximum degree of G. In this paper, the authors improve the lower bound and prove that G has at least m(G) edge-disjoint removable ears, where m(G) denotes the minimum number of perfect matchings needed to cover all edges of G.     

Triangle free graphs that are not 3-embeddable in Sd

A triangle free graph which cannot be $\text{3}$ embedded in a unit sphere is constructed. The construction uses the powerful orthogonal representation of graphs due to Lovász, and exhibits a strong connection between embeddability and Ramsey numbers. We also show that for every ε > 0 there is a triangle free graph G_ε that is not $\text{2+?}$ embeddable, thus settling Larman'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.     

A note on n-extendable graphs

A graph G having a perfect matching is called n-extendable if every matching of size n of G can be extended to a perfect matching. In this note, we show that if G is an n-extendable nonbipartite graph, then G + e is (n - 1)-extendable for any edge e ? E(G). © 1992 John Wiley & Sons, Inc.     

Matching structure and the matching lattice

The matching polyhedron, i.e., the convex hull of (incidence vectors of) perfect matchings of a graph was characterized by Edmonds; this result is the key to a large part of polyhedral combinatorics and is used in many combinatorial algorithms. The linear hull of perfect matchings was characterized by Naddef, and by Edmonds, Lovász, and Pulleyblank. In this paper we describe the lattice generated by these vectors, i.e., the set of all integer linear combinations of perfect matchings. It turns out that the Petersen graph is, in a sense, the only difficult example. Our results also imply a characterization of the linear hull of perfect matchings over fields of characteristic different from 0. The main method is a decomposition theory developed by Kotzig, Lovász, and Plummer, which breaks down every graph into a number of graphs called bricks with very good matching properties. The number of Petersen graphs among these bricks will turn out to be an essential parameter of the matching lattice. Some refinements of the decomposition theory are also given. Among others, we show that the list of bricks obtained during the decomposition procedure is independent of the special choices made during the procedure.     

The Colin de Verdière number and graphs of polytopes

The Colin de Verdière number µ(G) of a graph G is the maximum corank of a Colin de Verdière matrix for G (that is, of a Schrödinger operator on G with a single negative eigenvalue). In 2001, Lovász gave a construction that associated to every convex 3-polytope a Colin de Verdière matrix of corank 3 for its 1-skeleton.We generalize the Lovász construction to higher dimensions by interpreting it as minus the Hessian matrix of the volume of the polar dual. As a corollary, µ(G) ≥ d if G is the 1-skeleton of a convex d-polytope.Determination of the signature of the Hessian of the volume is based on the second Minkowski inequality for mixed volumes and on Bol’s condition for equality.     

Oriented matroids and Ky Fan’s theorem

L. Lovász (Matroids and Sperner’s Lemma, Europ. J. Comb. 1 (1980), 65–66) has shown that Sperner’s combinatorial lemma admits a generalization involving a matroid defined on the set of vertices of the associated triangulation. We prove that Ky Fan’s theorem admits an oriented matroid generalization of similar nature. Classical Ky Fan’s theorem is obtained as a corollary if the underlying oriented matroid is chosen to be the alternating matroid C ^m,r .     

Bounds for Generalized Thrackles

A thrackle (resp. generalized thrackle) is a drawing of a graph in which each pair of edges meets precisely once (resp. an odd number of times). For a graph with n vertices and m edges, we show that, for drawings in the plane, m≤ (2/3)(n-1) for thrackles, while m≤ 2n-2 for generalized thrackles. This improves theorems of Lovász, Pach, and Szegedy. The paper also examines thrackles in the more general setting of drawings on closed surfaces. The main result is: a bipartite graph G can be drawn as a generalized thrackle on a closed orientable connected surface if and only if G can be embedded in that surface. Received July 23, 1998, and in revised form January 1, 1999.     

Injective (Δ + 1)-coloring of planar graphs with girth 6

A vertex coloring of a graph G is called injective if every two vertices joined by a path of length 2 get different colors. The minimum number χ _i (G) of the colors required for an injective coloring of a graph G is clearly not less than the maximum degree Δ(G) of G. There exist planar graphs with girth g ≥ 6 and χ _i = Δ+1 for any Δ ≥ 2. We prove that every planar graph with Δ ≥ 18 and g ≥ 6 has χ _i ≤ Δ + 1.