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.

#### Invited Speakers

• Pavol Hell, Simon Fraser University, Canada
Obstruction Certificates for Geometrically Defined Graph (and Digraph) Classes (show abstract)

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 (show abstract)

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.

• Edita Máčajová, Comenius University, Bratislava, Slovakia
Point-line Configurations and Conjectures in Graph Theory (show abstract)

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.

A configuration $$\mathcal{C}=(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 $$\mathcal{C}=(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.

#### Past Meetings

Previous workshops in the series were held in:

#### Programme

A detailed schedule is now available.

#### Registration

Registration is now closed.

#### Accommodation

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

#### Travel

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.

Here is further information on travelling to Durham, and a map for finding your way in the city.

#### Registered Participants

A photographic record of a subset of those below.

• Thomas Bellitto (University of Bordeaux)
• Jan Bok (Charles University)
• Marston Conder (University of Auckland)
• Jiri Fiala (Charles University)
• Guillaume Fertin (University of Nantes)
• Pavol Hell (Simon Fraser University)
• Ioannis Ivrissimtzis (Durham University)
• Matthew Johnson (Durham University)
• Jan Karabas (Matej Bel University)
• Pavel Klavik (Charles University)
• Daniel Kral (University of Warwick)
• Jan Kratochvil (Charles University)
• Andrei Krokhin (Durham University)
• Edita Macajova (Comenius University)
• Barnaby Martin (Durham University)
• Tomas Masarik (Charles University)
• George Mertzios (Durham University)
• Iain Moffatt (Royal Holloway University of London)
• Jan Musilek (Charles University)
• Roman Nedela (Slovak Academy of Sciences)
• André Nichterlein (Durham University)
• Daniel Paulusma (Durham University)
• Jozef Siran (Open University)
• Martin Skoviera (Comenius University)
• Iain Stewart (Durham University)
• Stéphane Vialette (Université Paris-Est Marne la Vallée)
• Peter Zeman (Charles University and University of West Bohemia)

Contact: atcagc.2017@durham.ac.uk

Organizing committee:

We gratefully acknowledge financial support from Durham University and the London Mathematical Society.