TY - JOUR AB - For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs. AU - Campbell, Rutger AU - Hörsch, Florian AU - Moore, Benjamin ID - 15163 IS - 6 JF - Discrete Mathematics SN - 0012-365X TI - Decompositions into two linear forests of bounded lengths VL - 347 ER - TY - JOUR AB - The celebrated Erdős–Ko–Rado theorem about the maximal size of an intersecting family of r-element subsets of was extended to the setting of exterior algebra in [5, Theorem 2.3] and in [6, Theorem 1.4]. However, the equality case has not been settled yet. In this short note, we show that the extension of the Erdős–Ko–Rado theorem and the characterization of the equality case therein, as well as those of the Hilton–Milner theorem to the setting of exterior algebra in the simplest non-trivial case of two-forms follow from a folklore puzzle about possible arrangements of an intersecting family of lines. AU - Ivanov, Grigory AU - Köse, Seyda ID - 12680 IS - 6 JF - Discrete Mathematics SN - 0012-365X TI - Erdős-Ko-Rado and Hilton-Milner theorems for two-forms VL - 346 ER - TY - JOUR AB - The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one. AU - Silva, André AU - Arroyo Guevara, Alan M AU - Richter, Bruce AU - Lee, Orlando ID - 6638 IS - 11 JF - Discrete Mathematics SN - 0012-365X TI - Graphs with at most one crossing VL - 342 ER - TY - JOUR AB - We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the plane, they may be covered with n non-overlapping convex polygons with a total of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore, we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound on the number of slopes implies a new bound on a recently studied transversal problem. AU - Edelsbrunner, Herbert AU - Robison, Arch AU - Shen, Xiao ID - 4065 IS - 2 JF - Discrete Mathematics SN - 0012-365X TI - Covering convex sets with non-overlapping polygons VL - 81 ER - TY - JOUR AB - A set of m planes dissects E3 into cells, facets, edges and vertices. Letting deg(c) be the number of facets that bound a cellc, we give exact and asymptotic bounds on the maximum of ∈cinCdeg(c), if C is a family of cells of the arrangement with fixed cardinality. AU - Edelsbrunner, Herbert AU - Haussler, David ID - 4107 IS - C JF - Discrete Mathematics SN - 0012-365X TI - The complexity of cells in 3-dimensional arrangements VL - 60 ER -