Abstract. Recently, it was proved by Bérczi and Schwarcz that the problem of factorizing a matroid into rainbow bases with respect to a given partition of its ground set is algorithmically intractable. On the other hand, many special cases were left open. We first show that the problem remains hard if the matroid is graphic, answering a question of Bérczi and Schwarcz. As another special case, we consider the problem of deciding whether a given digraph can be factorized into subgraphs which are spanning trees in the underlying sense and respect upper bounds on the indegree of every vertex. We prove that this problem is also hard. This answers a question of Frank. In the second part of the article, we deal with the relaxed problem of covering the ground set of a matroid by rainbow bases. Among other results, we show that there is a linear function [Formula: see text] such that every matroid that can be factorized into [Formula: see text] bases for some [Formula: see text] can be covered by [Formula: see text] rainbow bases if every partition class contains at most 2 elements.

Bouchet conjectured in 1983 that each signed graph that admits a nowhere-zero flow has a nowhere-zero 6-flow. We prove that the conjecture is true for all signed series-parallel graphs. Unlike the unsigned case, the restriction to series-parallel graphs is nontrivial; in fact, the result is tight for infinitely many graphs.

Given a set S of points in the plane, the k-Gabriel graph of S is the geometric graph with vertex set S , where 𝑝 𝑖 , 𝑝 𝑗 ∈ 𝑆 are connected by an edge if and only if the closed disk having segment ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ ̅ 𝑝 𝑖 ⁢ 𝑝 𝑗 as diameter contains at most k points of 𝑆 ∖ { 𝑝 𝑖 , 𝑝 𝑗 } . We consider the following question: What is the minimum value of k such that the k -Gabriel graph of every point set S contains a Hamiltonian cycle? For this value, we give an upper bound of 10 and a lower bound of 2. The best previously known values were 15 and 1, respectively.

We prove that for any positive integer k, the edges of any graph whose fractional arboricity is at most $k + 1/(3k+2)$ can be decomposed into k forests and a matching. This is a partial result in the direction of the “Nine Dragon Tree” conjecture of Montassier et al.

Let [Formula: see text] denote the set of all odd cycle lengths of a graph [Formula: see text]. Gyárfás gave an upper bound for [Formula: see text] depending on the size of this set: if [Formula: see text], then [Formula: see text] unless some block of [Formula: see text] is a [Formula: see text], in which case [Formula: see text]. This bound is generally tight, but when investigating [Formula: see text] of special forms, better results can be obtained. Wang completely analyzed the case [Formula: see text]; Camacho proved that if [Formula: see text], [Formula: see text], then [Formula: see text]. We show that [Formula: see text] implies [Formula: see text].

We show that every pair of hexagons in a fullerene graph satisfying the isolated pentagon rule (IPR) forms a resonant pattern. This solves a problem raised by Ye, Qi, and Zhang [SIAM J. Discrete Math., 23 (2009), pp. 1023–1044].

The shortest cycle cover conjecture of Alon and Tarsi asserts that the edges of every bridgeless graph with m edges can be covered by cycles of total length at most $7m/5=1.400m$. We show that every cubic bridgeless graph has a cycle cover of total length at most $34m/21\approx1.619m$, and every bridgeless graph with minimum degree three has a cycle cover of total length at most $44m/27\approx1.630m$.

We prove that every cubic bridgeless graph G contains a 2-factor which intersects all (minimal) edge-cuts of size 3 or 4. This generalizes an earlier result of the authors, namely that such a 2-factor exists provided that G is planar. As a further extension, we show that every graph contains a cycle (a union of edge-disjoint circuits) that intersects all edge-cuts of size 3 or 4. Motivated by this result, we introduce the concept of a coverable set of integers and discuss a number of questions, some of which are related to classical problems of graph theory such as Tutte's 4-flow conjecture and the Dominating Cycle Conjecture.