It is a classic result that a set of n non-collinear points in the Euclidean plane defines at least n different lines. Chen and Chvátal conjectured in 2008 that the same results is true in metric spaces for an adequate definition of line. More recently, this conjecture was studied in the context of quasi-metric spaces. One way to study lines in an space is though its betweenness. Given a quasi-metric space (V,ρ), its induced quasi-metric be-tweenness is the set of triples (x, y, z) ϵ V3 such that ρ(x, z) = ρ(x, y) +ρ(y, z). In this work, we prove the existence of a quasi-metric space on four points a, b, c and d whose quasi-metric betweenness is ẞ = {(c, a, b), (a, b, c), (d, b, a), (b, a, d)}. This space has only three lines, none of which has four points. Moreover, we show that the betweenness of any quasi-metric space on four points with this property is isomorphic to B. Since B is not metric, we conclude that Chen and Chvatal's conjecture is valid for any metric space on four points.

A digraph D = (V, A) is semi-complete if for each pair of distinct vertices x and y in V, either xy or yx belong to A. A subset ℓ of vertices is a line of D if there are two distinct vertices x and y such that for any vertex z ε V, z ε ℓ if and only if a directed shortest path exists containing x, y and z. A classic result proved by Erdös says that any set of n points in the Euclidean plane endowed with the Euclidean distance defines a metric space with at least n different lines unless there is a line containing the n points. Chen and Chvátal in 2008 conjectured that the same results is true for any metric spaces where lines are defined in a manner similar to above. In this paper we prove that in any semi-complete digraphs with n vertices the number of lines defined by vertices connected by an arc is at least n. Then, the quasi-metric spaces defined by semi-complete digraphs fulfill Chen and Chvátal conjecture in a stronger manner as, on the one hand, they always have at least n lines, and on the other hand, these n lines are defined by vertices at distance one.

Abstract. The main result of this paper is the introduction of marked graphs and the marked graph polynomials ([Formula: see text]-polynomial) associated with them. These polynomials can be defined via a deletion-contraction operation. These polynomials are a generalization of the [Formula: see text]-polynomial, introduced by Noble and Welsh, and a specialization of the [Formula: see text]-polynomial, introduced by Ellis-Monaghan and Moffatt. In addition, we describe an important specialization of the [Formula: see text]-polynomial, which we call the [Formula: see text]-polynomial. Furthermore, we present an efficient algorithm for computing the chromatic symmetric function of a graph in the star basis of symmetric functions. As an application of these tools, we prove that proper trees of diameter at most 5 are reconstructible from its chromatic symmetric function.

It is well known that in finite graphs, large complete minors/topological minors can be forced by assuming a large average degree. Our aim is to extend this fact to infinite graphs. For this, we generalize the notion of the relative end degree, which had been previously introduced by the first author for locally finite graphs, and show that large minimum relative degree at the ends and large minimum degree at the vertices imply the existence of large complete (topological) minors in infinite graphs with countably many ends.