6 papers · 1 filter
A characterization of locally ordered ternary relations in terms of digraphs
Guillermo Gamboa Quintero, Martín Matamala, Juan Pablo Peña
In 1917, Huntington and Kline, followed by Huntington in 1924, studied systems of axioms for ternary relations aiming to capture the concepts of linear order (called betwenness) an…
Strong odd coloring in minor-closed classes
Miriam Goetze, Fabian Klute, Kolja Knauer +3
We show that the strong odd chromatic number on any proper minor-closed graph class is bounded by a constant. We almost determine the smallest such constant for outerplanar graphs.
Locally connected graphs: metric properties
Martín Matamala, Juan Pablo Peña, José Zamora
In this work we show that any connected locally connected graph defines a metric space having at least as many lines as vertices with only three exception: the complete multipartit…
Lines on digraphs of low diameter
Gabriela Araujo-Pardo, Martín Matamala, Juan P. Peña +1
A set of n non-collinear points in the Euclidean plane defines at least n different lines. Chen and Chvtal in 2008 conjectured that the same results is true in metric spaces for an…
A study on token digraphs
Cristina G. Fernandes, Carla N. Lintzmayer, Juan P. Peña +3
For a digraph of order and an integer , the -token digraph of is the graph whose vertices are all -subsets of vertices of and, given two su…
Quasimetric spaces with few lines
Guillermo Gamboa Quintero, Martín Matamala, Juan Pablo Peña
Chen and Chvátal conjectured in 2008 that in any finite metric space either there is a line containing all the points - a universal line -, or the number of lines is at least the n…