Submodular partition functions

Adapting the method introduced in Graph Minors X, we propose a new proof of the duality between the bramble number of a graph and its tree-width. Our approach is based on a new definition of submodularity on partition functions which naturally extends the usual one on set functions. The proof does not rely on Menger’s theorem, and thus generalises the original one. It thus provides a dual for matroid tree-width. One can also derive all known dual notions of other classical width-parameters from it.     

Bounded Tree-Width and LOGCFL

We show that (1) the recognition of tree-width bounded graphs and (2) the decidability of graph properties-which are defined by finite equivalence relations on h-sourced graphs-on tree-width bounded graphs belong to the complexity class LOGCFL. This is the lowest complexity class known for these problems. Our result complements the research in a series of papers by Arnborg, Bodlaender, Chandrasekharan, Courcelle, Hedetniemi, Lagergren, Proskurowski, Reed, Robertson, Seymour, Seese, and many others.     

New upper bounds on the decomposability of planar graphs

It is known that a planar graph on n vertices has branch‐width/tree‐width bounded by . In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for the case of tree‐width, α < 3.182 and for the case of branch‐width, α < 2.122. Our proof is based on the planar separation theorem of Alon, Seymour, and Thomas and some min–max theorems of Robertson and Seymour from the graph minors series. We also discuss some algorithmic consequences of this result. © 2005 Wiley Periodicals, Inc. J Graph Theory     

A short proof that every finite graph has a tree-decomposition displaying its tangles

We give a short proof that every finite graph (or matroid) has a tree-decomposition that displays all maximal tangles.This theorem for graphs is a central result of the graph minors project of Robertson and Seymour and the extension to matroids is due to Geelen, Gerards and Whittle.     

Extending the Greene-Kleitman theorem to directed graphs

The celebrated Dilworth theorem (Ann. of Math. 51 (1950), 161–166) on the decomposition of finite posets was extended by Greene and Kleitman (J. Combin. Theory Ser. A 20 (1976), 41–68). Using the Gallai-Milgram theorem (Acta Sci. Math. 21 (1960), 181–186) we prove a theorem on acyclic digraphs which contains the Greene-Kleitman theorem. The method of proof is derived from M. Saks' elegant proof (Adv. in Math. 33 (1979), 207–211) of the Greene-Kleitman theorem.     

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

On the cone of nonnegative circuits

We discuss three equivalent formulations of a theorem of Seymour on nonnegative sums of circuits of a graph, and present a different (but not shorter) proof of Seymour's resut.Research supported, in part, by an IBM Postdoctoral Fellowship, a grant of the Alexander von Humboldt-Stiftung, and NSF grant DMS-8504050.     

A Berge-keeping operation for graphs

We prove that a certain simple operation does not create odd holes or odd antiholes in a graph unless there are already some. In order to apply it, we need a vertex whose neighborhood has a coloring where the union of any two color classes is a connected graph; the operation is the shrinking of each of the color classes. Odd holes and antiholes do have such a vertex, and this property of minimal imperfect graphs implies the strong perfect graph theorem through the results of the paper. Conceivably, this property may be a target in the search for a proof of the strong perfect graph theorem different from the monumental achievement of Chudnovsky, Robertson, Seymour, and Thomas.     

Stokes Cocycle and Differential Galois Groups

The classification of germs of ordinary linear differential systems with meromorphic coefficients at 0 under convergent gauge transformations and fixed normal form is essentially given by the non-Abelian 1-cohomology set of Malgrange–Sibuya. (Germs themselves are actually classified by a quotient of this set.) It is known that there exists a natural isomorphism h between a unipotent Lie group (called the Stokes group) and the 1-cohomology set of Malgrange–Sibuya; the inverse map which consists of choosing, in each cohomology class, a special cocycle called a Stokes cocycle is proved to be natural and constructive. We survey here the definition of the Stokes cocycle and give a combinatorial proof for the bijectivity of h. We state some consequences of this result, such as Ramis, density theorem in linear differential Galois theory; we note that such a proof based on the Stokes cocycle theorem and the Tannakian theory does not require any theory of (multi-)summation.     

On unavoidable‐induced subgraphs in large prime graphs

Chudnovsky, Kim, Oum, and Seymour recently established that any prime graph contains one of a short list of induced prime subgraphs [1]. In the present article, we reprove their theorem using many of the same ideas, but with the key model‐theoretic ingredient of first determining the so‐called amount of stability of the graph. This approach changes the applicable Ramsey theorem, improves the bounds and offers a different structural perspective on the graphs in question. Complementing this, we give an infinitary proof that implies the finite result.     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

Hajós Theorem For Colorings Of Edge-Weighted Graphs

Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K _k by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101.     

Polynomial algorithms that prove an NP-Hard hypothesis implies an NP-hard conclusion

A number of results in hamiltonian graph theory are of the form “ implies ”, where is a property of graphs that is NP-hard and is a cycle structure property of graphs that is also NP-hard. An example of such a theorem is the well-known Chvátal–Erd s Theorem, which states that every graph G with κ is hamiltonian. Here κ is the vertex connectivity of G and is the cardinality of a largest set of independent vertices of G. In another paper Chvátal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than κ independent vertices. In this note we point out that other theorems in hamiltonian graph theory have a similar character. In particular, we present a constructive proof of a well-known theorem of Jung (Ann. Discrete Math. 3 (1978) 129) for graphs on 16 or more vertices.     

A New Proof of the Assmus–Mattson Theorem for Non-Binary Codes

C. Bachoc gave a new proof of theAssmus–Mattson theorem for linear binary codes using harmonicweight enumerators which she defined B. We give a new proof ofthe Assmus–Mattson theorem for linear codes over any finitefield using similar methods.     

The Klein bottle and multicommodity flows

LetG be an eulerian graph embedded on the Klein bottle. Then the maximum number of pairwise edge-disjoint orientation-reversing circuits inG is equal to the minimum number of edges intersecting all orientation-reversing circuits. This generalizes a theorem of Lins for the projective plane. As consequences we derive results on disjoint paths in planar graphs, including theorems of Okamura and of Okamura and Seymour.     

A new topological proof of the Abhyankar–Moh theorem

We present a new simple proof of the famous theorem of Abhyankar, Moh and Suzuki about rational curves in a plane. This proof relies on the Poincaré–Hopf theorem. This work was supported by Polish KBN Grant No 2 P03A 041 15Mathematics Subject Classification (2002):14E25.     

On even circuit decompositions of eulerian graphs

Let G be an eulerian graph without odd block. It was proved by P. D. Seymour that if G is planar, then E(G) has a circuit decomposition F such that each circuit of F is of even length. In this paper the theorem of Seymour is generalized: If G contains no subgraph contractible to K₅, then E(G) has an even circuit decomposition.     

Algorithms for finding distance-edge-colorings of graphs

For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.     

Branchings in rooted graphs and the diameter of greedoids

LetG be a 2-connected rooted graph of rankr andA, B two (rooted) spanning trees ofG We show that the maximum number of exchanges of leaves that can be required to transformA intoB isr ²–r+1 (r>0). This answers a question by L. Lovász.There is a natural reformulation of this problem in the theory ofgreedoids, which asks for the maximum diameter of the basis graph of a 2-connected branching greedcid of rankr.Greedoids are finite accessible set systems satisfying the matroid exchange axiom. Their theory provides both language and conceptual framework for the proof. However, it is shown that for general 2-connected greedoids (not necessarily constructed from branchings in rooted graphs) the maximum diameter is 2^r–1.     

Decomposition theorems

The countable-decomposition theorem for linear functionals has become a useful tool in the theory of representing measures (see [4–7]). The original proof of this theorem was based on a rather involved study of extreme points in the state space of a convex cone. Recently M. Neumann [9] gave an independent proof using a refined form of Simons convergence lemma and Choquet's theorem. In this paper a (relatively) short proof of an extension (to a more abstract situation) of the countable-decomposition theorem is given. Furthermore a decomposition criterion is obtained which even works in the case when not all states are decomposable. All the work is based on a complete characterization of those states which are partially decomposable with respect to a given sequence of sublinear functionals.