A workshop on Algebraic, Topological and Complexity Aspects of Graph Covers will be held in Durham from Monday 9 January to Friday 13 January 2017. The workshop’s main focus is on graph coverings and their applications in different areas of theoretical computer science and mathematics such as models of computation, computational complexity, and algebraic graph theory. The aim of the workshop is to bring together researchers working on these diverse aspects of graph coverings, and to provide an opportunity for them to introduce their approaches and results to one another and to try to pursue joint research. We plan a small number of survey talks, several open problem sessions, and ample time for discussions and problem solving.
Pavol Hell, Simon Fraser University, Canada Obstruction Certificates for Geometrically Defined Graph (and Digraph) Classes
In this talk I will focus on obstruction characterizations for interval graphs and their analogues, principally versions of interval bigraphs, interval digraphs, and circular arc-graphs. I will propose a new geometrically defined class of digraphs that generalizes the first three classes, and present an obstruction characterization for it. I will also present a separate obstruction characterization for the class of circular-arc graphs, that gives an answer to a question of Klee, and of Hadwiger and Debrunner, from the early 1960’s. The first three classes are closely related to the complexity of the list homomorphism problem.
This is joint with T. Feder, J. Huang, and A. Rafiey for the interval graphs and their generalizations, and with M. Francis and J. Stacho for the circular arc graphs.
Daniel Kráľ, University of Warwick, UK Subgraph Counts in Large Graphs
Many problems in extremal graph theory relate to understanding possible combinations of densities of subgraphs in large graphs. A recent breakthrough is Razborov’s solution of the edge vs. triangle density problem (proving an old conjecture of Lovász and Simonovits, which has been extended by Nikiforov to complete graphs of order four and by Reiher to complete graphs of an arbitrary order. In this talk, we survey results in this area and report on our results on densities of 3-vertex graphs.
The talk contains results based on a joint work with Roman Glebov, Andrzej Grzesik, Ping Hu, Tamás Hubai and Jan Volec.
Many open problems in Graph Theory can be reduced to the family of cubic graphs. Moreover, in a lot of cases it is enough to focus on an even smaller set of graphs – snarks, which are cubic graphs which do not admit a proper 3-edge-colouring.
Edita Máčajová, Comenius University, Bratislava, Slovakia Point-line Configurations and Conjectures in Graph Theory
A configuration =(P,B) consists of a finite set P of points and a finite set B of blocks. Blocks are 3-element subsets of P such that for each pair of points of P there is at most one block in B which contains both of them.
A colouring of a cubic graph G with a configuration =(P,B) is an assignment of an element from P to each edge of G such that the three points that meet at any vertex form a block of B.
During this talk we will discuss several well known conjectures and open problems from the view of colouring with configurations and thereby provide an unifying view of them. These problems include the Fulkerson Conjecture and the Petersen Coloring Conjecture, the Fan-Raspaud Conjecture, problems concerting the perfect matching index of a graph and others.
Delegates should make their own arrangements for accommodation from the university or using local hotels. We make a number of suggestions and note that it is advisable to book early. A much wider selection can be found at this is durham
Durham is easy to reach by train or air. There are frequent train services to London (about 3 hours) and Edinburgh (about 2 hours). There are two international airports (Newcastle and Durham Tees Valley) with good connections to Durham. They offer cheap flight services to several destinations.