European Journal of Combinatorics

Let G be a finite abelian group. A nonempty subset A in G is called a basis of order h if h A = G; when h A ≠ G, it is called a nonbasis of order h. Our interest is in all possible sizes of h A when A is a nonbasis of order h in G of maximum size;...

In 1989, Rota conjectured that, given n bases B 1 , … , B n of the vector space F n over some field F, one can always decompose the multi-set B 1 ∪ ⋯ ∪ B n into transversal bases. This conjecture remains wide open despite of a lot of attention. ...

We prove that there are O ( n ) tangencies among any set of n red and blue planar curves in which every pair of curves intersects at most once and no two curves of the same color intersect. If every pair of curves may intersect more than once, ...

Lehel conjectured in the 1970s that the vertices of every red and blue edge-coloured complete graph can be partitioned into two monochromatic cycles. This was confirmed in 2010 by Bessy and Thomassé. However, the host graph G does not have to be ...

Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes ...

The theme of this article is a “reciprocity” between bounded up-down paths and bounded alternating sequences. Roughly speaking, this “reciprocity” manifests itself by the fact that the extension of the sequence of numbers of paths of length n, ...

We will state 10 problems, and solve some of them, for partitions in triangle-free graphs related to Erdős’ Sparse Half Conjecture.

Among others we prove the following variant of it: For every sufficiently large even integer n the following ...

Embedding graphs in a geographical or latent space, i.e. inferring locations for vertices in Euclidean space or on a smooth manifold or submanifold, is a common task in network analysis, statistical inference, and graph visualization. We consider ...

A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x , y and z with x + y = z. We study the following problem: how many random integers from [ n ] need to be added to some A ⊆ [ n ] to ensure with high ...

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph G and weight function w : V ( G ) → Q ≥ 0, the Split Vertex Deletion (SVD) problem asks to find a minimum weight set of vertices X such ...

Consider a graph G drawn on a fixed surface, and assign to each vertex a list of colors of size at least two if G is triangle-free and at least three otherwise. We prove that we can give each vertex a color from its list so that each ...

Motivated by recent results on quasi-Stirling permutations, which are permutations of the multiset { 1 , 1 , 2 , 2 , … , n , n } that avoid the “crossing” patterns 1212 and 2121, we consider nonnesting permutations, defined as those that avoid ...

Recent results show that several important graph classes can be embedded as subgraphs of strong products of simpler graphs classes (paths, small cliques, or graphs of bounded treewidth). This paper develops general techniques to bound the ...

Let G be a graph obtained as the union of some n-vertex graph H n with minimum degree δ ( H n ) ≥ α n and a d-dimensional random geometric graph G d ( n , r ). We investigate under which conditions for r the graph G will a.a.s. contain the kth ...