27 Sep 2024 at 10:00
Speaker: Francesco Verciani (Universität Kassel)
Title: Flips in colourful triangulations
Abstract: The associahedron is the graph G_N that has as nodes all triangulations of a convex N-gon, and an edge between any two triangulations that differ in a flip operation. A flip removes an edge shared by two triangles and replaces it by the other diagonal of the resulting 4-gon. We consider a large collection of induced subgraphs of G_N obtained by Ramsey-type colourability properties. Specifically, colouring the points of the N-gon red and blue alternatingly, we consider only colourful triangulations, namely triangulations in which every triangle has points in both colours, i.e., monochromatic triangles are forbidden. We prove that the resulting induced subgraph F_N has a Hamilton cycle for all N>7, resolving a problem raised by Sagan, i.e., all colourful triangulations on N points can be listed so that any two cyclically consecutive triangulations differ in a flip. In fact, we prove that for an arbitrary fixed colouring pattern of the N points with at least 10 changes of colour, the resulting subgraph of G_N on colourful triangulations (for that colouring pattern) admits a Hamilton cycle.
This is joint work with Rohan Acharya (University of Warwick) and Torsten Mütze (Universität Kassel)
04 Oct 2024 at 10:00
Speaker: Péter Ágoston(Alfréd Rényi Institute of Mathematics)
Title: Ordered Yao graphs
Abstract: Take a finite point set P⊂R^2 and for all p∈P, divide the plane into k cones (“sectors”) having apex angle 2π/k so that the directions of the bounding rays are the same for all p∈P. Given an ordering on the points of P, connect p with the point closest to it from all the sectors around it out of the points that are preceding p in the ordering (if such a point exists in a certain sector) and call the resulting graph a k-sector ordered Yao graph. The motivation behind these graphs is that they are spanners with relatively few edges and relatively small Euclidean path-lengths. We study several extremal values (maximum degree, edge number and clique number) of ordered Yao graphs, where the values are taken over all orderings on a fixed set of points. We also study 1-sector ordered Yao graphs (also called ordered nearest neighbour graphs) in R^d and in general metric spaces.
This is joint work with Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh and Ji Zeng.
11 Oct 2024 at 10:00
Speaker: Robert Scheffler (Brandenburg University of Technology).
Title: Graph Search Trees and the Intermezzo Problem
Abstract: The last in-tree recognition problem asks whether a given spanning tree can be derived by connecting each vertex with its rightmost left neighbor of some search ordering. In this study, we demonstrate that the last-in-tree recognition problem for Generic Search is NP-complete. We utilize this finding to strengthen a complexity result from order theory. Given a partial order π and a set of triples, the NP-complete intermezzo problem asks for a linear extension of π where each first element of a triple is not between the other two. We show that this problem remains NP-complete even when the Hasse diagram of the partial order forms a tree of bounded height. In contrast, we give an XP-algorithm for the problem when parameterized by the width of the partial order. Furthermore, we show that - under the assumption of the Exponential Time Hypothesis - the running time of this algorithm is asymptotically optimal.
This is joint work with Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, and Martin Strehler.
18 Oct 2024 at 10:00
Speaker: Jan Jedelský (Masaryk University, Brno, Czech republic).
Title: Hereditary Graph Product Structure Theory and Induced Subgraphs of Strong Products
Abstract: Dujmović et al., in their seminal paper, describe the global structure of planar graphs by showing that any planar graph is a subgraph of the strong product of a path and a graph of small tree-width. This so-called Planar Product Structure Theorem has led to many recent breakthroughs and has been generalized to many sparse graph classes related to planar graphs. In this talk, we will discuss how one can strengthen and generalize the notion of having a product structure to dense and hereditary settings. We will consider replacing the subgraph relation by the induced subgraph relation and possibly also tree-width by clique-width. In doing so, we will use a new graph parameter -- H-clique-width -- which provides another view of a graph being isomorphic to an induced subgraph of the strong product of a path and a graph of small clique-width. We will also consider the possibility of replacing paths by an arbitrary class of bounded degree graphs. This is joint work with Petr Hliněný.
25 Oct 2024 at 10:00
Speaker: Debajyoti Mondal(University of Saskatchewan)
Title:
Abstract: