PLANarity and distance IN Graph theory

Our project aims at investigating four important questions of metric or topological nature in graph theory. The first question is related to a classical result which follows from the Sylvester-Gallai theorem: every non-collinear set of n points in the Euclidean plane determines at least n lines. The notion of “betweenness” allows the notion of line to be extended to every metric space, and it has been conjectured, by Chen and Chvátal, that this result can be extended as well to every metric space. This conjecture is open for metric spaces induced by general graphs, and we aim at developing tools towards solving it by studying particular classes of graphs. The second question is related to the study of vertex colorings with conditions on distance. We will consider colorings which require different colors for vertices at distance (exactly) p, for some fixed p. Considering such a coloring for a graph G amounts to considering a proper coloring of the exact distance graph of G, which has the same vertex set as G and an edge between x and y if and only if these vertices are at distance p in G. For that type of colouring, the answer to the question “how many colours suffice?", can depend greatly on the parity of p. In particular, a finite number of colors suffice if p is odd and we consider planar graphs. We aim at tackling different open problems related to this type of colorings, particularly on planar graphs. The study of cliques in exact distance graphs also interests us as it is surprisingly related to the existence of projective geometries. The third deals with the following decision problem: Given a positive integer k and a planar graph G, is the k × k grid a minor of G? We aim to determine whether this decision problem is NP-complete. Since the Grid-Minor Theorem of Robertson and Seymour, roughly states that graphs of large tree-width necessarily contain large grid minors, this problem is related to a central problem of planar graphs: can we effectively compute the tree-width of a planar graph? We hope that our investigations can bring light to this important question as well. Finally, the fourth problem is about dominating sets in planar graphs. In particular, we try to attack the following conjecture, attributed to Matheson and Tarjan: there is a dominating set with at most n/4 vertices in any planar triangulation on n vertices. This conjecture has been settled for planar triangulations of maximum degree 6; and there are related results for hamiltonian planar triangulations and outerplanar graphs. The best known upper bound for the general case is 17n/53. We are interested in obtaining new upper bounds for the size of a dominating set in planar triangulations or subclasses of them.

GUTIERREZ ALVA ,JUAN GABRIEL