Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

Characterizing graphic matroids by a system of linear equations

Given a rank-r   binary matroid we construct a system of O(r³)$O(r^3)$ linear equations in O(r²)$O(r^2)$ variables that has a solution over GF(2)$\mathrm{GF}(2)$ if and only if the matroid is graphic.     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

One‐way infinite 2‐walks in planar graphs

We prove that every 3‐connected 2‐indivisible infinite planar graph has a 1‐way infinite 2‐walk. (A graph is 2‐indivisible if deleting finitely many vertices leaves at most one infinite component, and a 2‐walk is a spanning walk using every vertex at most twice.) This improves a result of Timar, which assumed local finiteness. Our proofs use Tutte subgraphs, and allow us to also provide other results when the graph is bipartite or an infinite analog of a triangulation: then the prism over the graph has a spanning 1‐way infinite path.     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs

We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010     

Codiameters of 3‐connected 3‐domination critical graphs

A graph G is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a 3‐connected 3‐domination critical graph of order n. In this paper, we show that there is a path of length at least n?2 between any two distinct vertices in G and the lower bound is sharp. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 76–85, 2002     

Hamiltonian N2‐locally connected claw‐free graphs

A graph G is N₂‐locally connected if for every vertex ν in G, the edges not incident with ν but having at least one end adjacent to ν in G induce a connected graph. In 1990, Ryjá?ek conjectured that every 3‐connected N₂‐locally connected claw‐free graph is Hamiltonian. This conjecture is proved in this note. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 142–146, 2005     

Planar graphs with neither 5‐cycles nor close 3‐cycles are 3‐colorable

In 2003, O. V. Borodin and A. Raspaud conjectured that every planar graph with the minimum distance between triangles, d_Δ, at least 1 and without 5‐cycles is 3‐colorable. This Bordeaux conjecture (Brdx3CC) has common features with Havel's (1970) and Steinberg's (1976) 3‐color problems. A relaxation of Brdx3CC with d_Δ?4 was confirmed in 2003 by Borodin and Raspaud, whose result was improved to d_Δ?3 by Borodin and A. N. Glebov (2004) and, independently, by B. Xu (2007). The purpose of this article is to make the penultimate step (d_Δ?2) towards Brdx3CC. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 1–31, 2010     

Minors in large almost‐5‐connected non‐planar graphs

It is shown that every sufficiently large almost‐5‐connected non‐planar graph contains a minor isomorphic to an arbitrarily large graph from one of six families of graphs. The graphs in these families are also almost‐5‐connected, by which we mean that they are 4‐connected and all 4‐separations contain a “small” side. As a corollary, every sufficiently large almost‐5‐connected non‐planar graph contains both a K_{3, 4}‐minor and a ‐minor. The connectivity condition cannot be reduced to 4‐connectivity, as there are known infinite families of 4‐connected non‐planar graphs that do not contain a K_{3, 4}‐minor. Similarly, there are known infinite families of 4‐connected non‐planar graphs that do not contain a ‐minor.     

Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

Connectivity keeping trees in k‐connected graphs

We show that one can choose the minimum degree of a k‐connected graph G large enough (independent of the vertex number of G) such that G contains a copy T of a prescribed tree with the property that G ? V(T) remains k‐connected. This was conjectured in [W. Mader, J Graph Theory 65 (2010), 61–69]. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 324–329, 2012     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

Circuits through prescribed vertices in k‐connected k‐regular graphs

We show that every set of vertices in a k‐connected k‐regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145–163, 2002     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

A characterization of weakly four‐connected graphs

A graph G = (V, E) is called weakly four‐connected if G is 4‐edge‐connected and G ? x is 2‐edge‐connected for all x ∈ V. We give sufficient conditions for the existence of ‘splittable’ vertices of degree four in weakly four‐connected graphs. By using these results we prove that every minimally weakly four‐connected graph on at least four vertices contains at least three ‘splittable’ vertices of degree four, which gives rise to an inductive construction of weakly four‐connected graphs. Our results can also be applied in the problem of finding 2‐connected orientations of graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 217–229, 2006     

Minor‐universal planar graphs without accumulation points

We show that the countably infinite union of infinite grids, H say, is minor‐universal in the class of all graphs that can be drawn in the plane without vertex accumulation points, i.e., that H contains every such graph as a minor. Furthermore, we characterize the graphs that occur as minors of the infinite grid by a natural topological condition on their embeddings. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 1–7, 2001     

Relative length of longest paths and cycles in 3‐connected graphs

For a graph G, let p(G) denote the order of a longest path in G and c(G) the order of a longest cycle in G, respectively. We show that if G is a 3‐connected graph of order n such that for every independent set {x₁, x₂, x₃, x₄}, then G satisfies c(G) ≥ p(G) ? 1. Using this result, we give several lower bounds to the circumference of a 3‐connected graph. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 137–156, 2001