We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every 4-edge-connected graph $G$ and every $r\in V(G)$, there is a set of four spanning trees of $G$ with the following property. For every vertex in $G$, the unique paths back to $r$ in each tree are edge-disjoint. Our proof implies a polynomial-time algorithm for constructing the trees.

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nešetřil and Ossona de Mendez on the existence of low tree-depth colorings.

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct anO(nlogn) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product, we give a yet simpler proof of Grötzsch's theorem.

We present a linear-time algorithm for deciding first-order logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no sub graph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We also develop an almost linear-time algorithm for deciding FOL properties in classes of graphs with locally bounded expansion, those include classes of graphs with locally bounded tree-width or locally excluding a minor. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FOL property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their addition results in a graph in the class. In addition, we design a dynamic data structure for testing existential properties or the existence of short paths between prescribed vertices in such classes of graphs. All our results also hold for relational structures and are based on the seminal result of Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.

Gimbel and Thomassen asked whether 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface which combined with previous results gives a linear-time algorithm to compute the chromatic number of such graphs. Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface Σ guarantees the existence of a subgraph H, whose size depends only on Σ, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the “winding number” of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends to find a 3-coloring. If the input triangle-free graph G drawn in Σ is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates Σ then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.

Grötzsch's theorem states that every triangle-free planar graph is 3-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a 3-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an O(n log n) algorithm). We design a linear-time algorithm to find a 3-coloring of a given triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give a yet simpler proof of Grötzsch's theorem.

We give a polynomial-time algorithm for the following problem of P61ya.Given an n x n O-1 matrix, either find a matrix obtained from it by changing some of the 1's to -1's in such a way that the determinant of the new matrix equals the permanent of the old one, or determine that no such matrix exists.This is equivalent to finding Pfafiian orientations of bipartite graphs and to the even circuit problem for directed graphs.The aigorithm is based on a structural characterization of bipartite graphs that admit a Pfaffian orientation.-

Article Free Access Share on Efficiently four-coloring planar graphs Authors: Neil Robertson Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Daniel P. Sanders Department of Mathematics, The Ohio State University, Columbus, Ohio Department of Mathematics, The Ohio State University, Columbus, OhioView Profile , Paul Seymour Bellcore, 445 South Street, Morristown, New Jersey Bellcore, 445 South Street, Morristown, New JerseyView Profile , Robin Thomas School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia School of Mathematics, Georgia Institute of Technology, Atlanta, GeorgiaView Profile Authors Info & Claims STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of ComputingJuly 1996 Pages 571–575https://doi.org/10.1145/237814.238005Published:01 July 1996Publication History 63citation2,172DownloadsMetricsTotal Citations63Total Downloads2,172Last 12 Months487Last 6 weeks60 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors give a short proof of a theorem of Lipton and Tarjan, that, for every planar graph with $n > 0$ vertices, there is a partition $( A,B,C )$ of its vertex set such that $|A|,|B| < \frac{2}{3}n,|C| \leq 2( 2n )^{1/2} $, and no vertex in A is adjacent to any vertex in B Secondly, they apply the same technique more carefully to deduce that, in fact, such a partition $( A,B,C )$ exists with $|A|,|B| < \frac{2}{3}n$, and $|C| \leq \frac{3}{2}( 2n )^{1/2} $ ; this improves the best previously known result. An analogous result holds when the vertices or edges are weighted.

corresponds to G in time 0(n3/2).We also describe Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H.We prove that there is a set X of no more than h3/2nl/2 vertices of G whose deletion creates a graph in which the total weight of every connected component is at most 1/2.This extends significantly a well-known theorem of Lipton and Tarjan for planar graphs.We exhibit an algorithm which finds, given an n-vertex graph G with weights as above and an h-vertex graph H, either such a set X or a minor of G isomorphic to H.The algorithm runs in time O(hl/2nl/2m), where m is the number of edges of G plus the number of its vertices.Our results supply extensions of the many known applications of the Lipton-Tarjan separator theorem from the class of planar graphs (or that of graphs with bounded genus) to any class of graphs with an excluded minor.For example, it follows that for any fixed graph H, given a graph G with n vertices and with no H-minor one can approximate the size of the maximum independent set of G up to a relative error of 1/~/l-b-~ in polynomial time, find that size exactly and find the chromatic number of G in time 2 °(¢'~-) and solve any sparse system of n linear equations in n unknowns whose sparsity structure Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery.To copy otherwise, or to republish, requires a fee and/or specific