Abstract. Ramsey proved that for every positive integer [Formula: see text], every sufficiently large graph contains an induced [Formula: see text] or [Formula: see text]. Among the many extensions of Ramsey’s theorem, there is an analogue for connected graphs: For every positive integer [Formula: see text], every sufficiently large connected graph contains an induced [Formula: see text], [Formula: see text], or [Formula: see text]. In this paper, we establish an analogue for 2-connected graphs. In particular, we prove that for every integer exceeding two, every sufficiently large 2-connected graph contains one of the following as an induced subgraph: [Formula: see text], a subdivision of [Formula: see text], a subdivision of [Formula: see text] with an edge between the two vertices of degree [Formula: see text], and a well-defined structure similar to a ladder.

Abstract. Let [Formula: see text] be a multigraph. The cover index [Formula: see text] of [Formula: see text] is the greatest integer [Formula: see text] for which there is a coloring of [Formula: see text] with [Formula: see text] colors such that each vertex of [Formula: see text] is incident with at least one edge of each color. Let [Formula: see text] be the minimum degree of [Formula: see text], and let [Formula: see text] be the codensity of [Formula: see text], defined by [Formula: see text], where [Formula: see text] is the set of all edges of [Formula: see text] with at least one end in [Formula: see text]. It is easy to see that [Formula: see text]. In 1978, Gupta proposed the following codensity conjecture: Every multigraph [Formula: see text] satisfies [Formula: see text], which is the dual version of the Goldberg–Seymour conjecture on edge-colorings of multigraphs. In this note, we prove that [Formula: see text] if [Formula: see text] is not integral and [Formula: see text] otherwise. We also show that this codensity conjecture implies another conjecture concerning the cover index made by Gupta in 1967.

A sufficiently large connected matroid $M$ contains a big circuit or a big cocircuit. Wu showed that we can ensure that $M$ has a big circuit or a big cocircuit containing any chosen element of $M$. In this paper, we prove that, for a fixed connected matroid $N$, if $M$ is a sufficiently large connected matroid having $N$ as a minor, then, up to duality, either $M$ has a big connected minor in which $N$ is a spanning restriction and the deletion of $E(N)$ is a large connected uniform matroid, or $M$ has, as a minor, the $2$-sum of a big circuit and a connected single-element extension or coextension of $N$. In addition, we find a set of unavoidable minors for the class of graphs that have a cycle and a bond with a big intersection.

Tree-width and path-width are two important graph parameters introduced by Robertson and Seymour in their famous Graph Minors project. For a fixed positive integer $k$, the classes of graphs of tree-width at most $k$, and path-width at most $k$, are both minor-closed. However, their complete characterizations in terms of excluded minors are known only for $k \leqslant 3$ for tree-width, and for $k \leqslant 2$ for path-width. It is known that the number of excluded minors for the class of graphs of path-width $\leqslant k$ is 2 if $k = 1$; $110$ if $k = 2$; and $\geqslant 122$ million if $k = 3$. Barát et. al. [Studia Sci. Math. Hungar., 49 (2012), pp. 211--222] showed that the class of graphs of path-width $\leqslant 2$, restricted to its 2-connected members, can be characterized by only three excluded minors, and asked whether a similar result may be obtained for 3-connected graphs of path-width $\leqslant 3$. We answer this question in the affirmative by characterizing this class by five excluded minors.

Given a preference system $(G, \prec)$ and an integral weight function defined on the edge set of $G$ (not necessarily bipartite), the maximum-weight stable matching problem is to find a stable matching of $(G, \prec)$ with maximum total weight. In this paper we study this $NP$-hard problem using linear programming and polyhedral approaches. We show that the Rothblum system for defining the fractional stable matching polytope of $(G, \prec)$ is totally dual integral if and only if this polytope is integral if and only if $(G, \prec)$ has a bipartite representation. We also present a combinatorial polynomial-time algorithm for the maximum-weight stable matching problem and its dual on any preference system with a bipartite representation. Our results generalize Király and Pap's theorem on the maximum-weight stable-marriage problem and rely heavily on their work.

A 3-connected graph is called $3^+$-connected if it has no 3-separation that separates a “large” fan or $K_{3,n}$ from the rest of the graph. It is proved in this paper that except for $K_4$, every $3^+$-connected graph has a $3^+$-connected proper minor that is at most two edges away from the original graph. This result is used to characterize Q-minor-free graphs, where Q is obtained from the cube by contracting an edge.

We recently proposed the Edgewise Greedy Algorithm (EGA) for learning a decomposable Markov network of treewidth k approximating a given joint probability distribution of n discrete random variables. The main ingredient of our algorithm is the stepwise forward selection algorithm (FSA) due to Deshpande, Garofalakis, and Jordan. EGA is an efficient alternative to the algorithm (HGA) by Malvestuto, which constructs a model of treewidth k by selecting hyperedges of order k+1. In this paper, we present results of empirical studies that compare HGA, EGA and FSA-K which is a straightforward application of FSA, in terms of approximation accuracy (measured by KL-divergence) and computational time. Our experiments show that (1) on the average, all three algorithms produce similar approximation accuracy; (2) EGA produces comparable or better approximation accuracy and is the most efficient among the three. (3) Malvestuto's algorithm is the least efficient one, although it tends to produce better accuracy when the treewidth is bigger than half of the number of random variabls; (4) EGA coupled with local search has the best approximation accuracy overall, at a cost of increased computation time by 50 percent.

Wavelengths and converters are shared by communication requests in optical networks. The usage of converters increases the utilization of wavelengths and allows more requests to succeed. The converters usage problem (CUP) is to determine the minimum number of converter so that each node can send messages to all the others (broadcasting). In this paper, we study the CUP in sparse conversion networks with bounded treewidth. A converter wavelength-dominates a node if there is a uniform wavelength path between them. The minimal wavelength dominating set problem (MWDSP) is to locate the minimum number of converters so that all the other nodes in the network are wavelength-dominated. We use a linear complexity dynamic programming algorithm to solve the MWDSP for networks with bounded treewidth. One such solution provides a low bound for the optimal solution to the CUP.

Abstract Let 𝒢 be a class of graphs that is closed under taking topological minors. We derive in this paper some necessary and sufficient conditions for the existence of a polynomial p(n) such that t(G) ≤ p(|E(G)|) for all graphs G in 𝒢, where t(G) is the number of spanning trees of G.

Let $D = ( V,A )$ be a directed planar graph, let $( r_1 ,s_1 ), \cdots , ( r_k ,s_k )$ be pairs of vertices on the boundary of the unbounded face, let $A_1 , \cdots ,A_k $ be subsets of A, and let H be a collection of unordered pairs from $\{ 1, \cdots ,k \}$. Given are necessary and sufficient conditions for the existence of a directed $r_i - s_i $ path $P_i $ in $( V,A_i )$ (for $i = 1, \cdots ,k$), such that $P_i $ and $P_j $ are vertex-disjoint whenever $\{ i, j \} \in H$.