Abstract. We consider the following variant of the edge-augmentation problem: Given a [Formula: see text]-edge-connected graph with no loops or multiple edges, find a smallest edge set in the complement whose addition to [Formula: see text] results in a [Formula: see text]-edge-connected graph. We establish the following dichotomy for this problem: If the complement of [Formula: see text] contains a matching covering all vertices of [Formula: see text]-degree [Formula: see text] (and possibly more), then the complement also contains a matching whose addition to [Formula: see text] results in a [Formula: see text]-edge-connected graph. A smallest matching which augments the minimum degree can be found, in polynomial time, by Edmonds’ matching algorithm, but it need not augment the edge-connectivity. Indeed, it is NP-hard to find a smallest edge-connectivity augmenting edge set, by a result of Tibor Jordán. On the other hand, if the complement of [Formula: see text] contains no matching covering all vertices of [Formula: see text]-degree [Formula: see text], then the complement has a minimum degree augmenting path system consisting of paths of length 1 or 2. Again we can find such a path system with as few edges as possible by Edmonds’ matching algorithm. We can, in polynomial time, modify it to an edge-connectivity augmenting path system of paths of length 1 or 2 with the same number of edges, and this time it yields a smallest edge-connectivity augmenting set of edges. Combining these results, we conclude that a smallest edge-connectivity augmenting edge set in the complement of a [Formula: see text]-regular, [Formula: see text]-edge-connected simple graph has size [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text], and [Formula: see text] is the size of a maximum matching in the complement of [Formula: see text]. Another corollary is that the complement of every simple noncomplete graph [Formula: see text] with [Formula: see text] vertices has a set of at most [Formula: see text] edges whose addition to [Formula: see text] results in a graph of larger edge-connectivity, with equality holding if and only the complement of [Formula: see text] is a disjoint union of 3-cycles.

A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph’s edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^{3/4}) when α is at most polylogarithmic in n. Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^{5/7}), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time. However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^{1/2}) time.

We study methods for finding strict upper bounds on the fractional chromatic number $\chi_f(G)$ of a graph $G$. We illustrate these methods by providing short proofs of known inequalities in connection with Grötzsch's 3-color theorem and the 5-color theorem for planar graphs. We also apply it to $d$-degenerate graphs and conclude that every $K_{d+1}$-free $d$-degenerate graph with $n$ vertices has independence number $ 0$, the fractional chromatic number of any graph embedded on $S$ of sufficiently large width (depending only on $S$ and $\varepsilon$) is at most $4+\varepsilon$. In the same spirit we prove that Eulerian triangulations or triangle-free graphs of large width have $\chi_f\le 3+\varepsilon$, and quadrangulations of large width have $\chi_f\le 2+\varepsilon$. While the $\varepsilon$ is needed in the latter two results, we conjecture that in the first result $4+\varepsilon$ can be replaced by 4. The upper bounds $\chi_f\le 4+\varepsilon$, $\chi_f\le 3+\varepsilon$, $\chi_f\le 2+\varepsilon$, respectively, are already known for graphs on orientable surfaces, but our results are also valid for graphs on nonorientable surfaces. Surprisingly, a strict lower bound on the fractional chromatic number may imply an upper bound on the chromatic number: Grötzsch's theorem implies that every 4-chromatic planar graph $G$ has fractional chromatic number $\chi_f(G)\ge 3$. We conjecture that this inequality is always strict and observe that this implies the 4-color theorem for planar graphs.

Fleischner's theorem says that the square of every 2-connected graph contains a Hamiltonian cycle. We present a proof resulting in an O(|E|) algorithm for producing a Hamiltonian cycle in the square G2 of a 2-connected graph G = (V, E). The previous best was O(|V|2) by Lau in 1980. More generally, we get an O(|E|) algorithm for producing a Hamiltonian path between any two prescribed vertices, and we get an O(|V|2) algorithm for producing cycles C3, C4, …, C|V| in G2 of lengths 3,4, …, |V|, respectively.

We prove that it is NP-hard to determine whether the crossing number of an input graph is even or odd.

We prove that the problem of finding a cycle cover of smallest total length is NP-hard. This confirms a conjecture of Itai, Lipton, Papadimitriou, and Rodeh from 1981.

This paper presents polynomially bounded algorithms for finding a cycle through any two prescribed arcs in a semicomplete digraph and for finding a cycle through any two prescribed vertices in a complete k-partite oriented graph. It is also shown that the problem of finding a maximum transitive subtournament of a tournament and the problem of finding a cycle through a prescribed arc set in a tournament are both NP-complete.