School of Engineering and Computing Sciences
Algebraic, Topological and Complexity Aspects of Graph Covers 2017
All talks are in Room E240 in the Higginson Building of the School of Engineering and Computing Sciences. This room (and others if needed) are available for working, discussing and problem solving throughout the week. Tea/Coffee and Lunches are in the Atrium and Coffee Room in the same building. The registration desk will be located in the Atrium near to the entrance of the building.
Delegates should make their own arrangements for evening meals. There is a wide range of restaurants nearby in the city centre. Here is a map for finding your way in the city: the School is number 14, Durham Castle (also known as University College) is number 23 and Palace Green Library is number 22.
Monday 9 January
09000930 
Registration  
09300935  Welcome to Durham  
09351030  Pavol Hell  Obstruction Certificates for Geometrically Defined Graph (and Digraph) Classes (show abstract) Slides In this talk I will focus on obstruction characterizations for interval graphs and their analogues, principally versions of interval bigraphs, interval digraphs, and circular arcgraphs. 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 circulararc 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. 
10301100  Tea/Coffee  
11001230  Open Problems show/hide all texts
Problem 1: Snarks, problem, author, text It can be easily seen that given covering \(X\to Y\) between graphs, a nowherezero \(k\)flow defined on \(Y\) lifts to a nowherezero \(k\)flow of \(X\). In particular, if both \(X\) and \(Y\) are cubic graphs we get: if \(Y\) is 3edgecolourable, then \(X\) is 3edgecolourable as well. A general problem reads as follows: Problem 1.i: Characterise non3edgecolourable cubic graphs covering the dumbell graph DB, a 2vertex cubic graph with two loops attached to the two vertices and an edge joining the two vertices. The above general problem includes the following two subproblems. A permutation graph is a cubic graph which contains two induced cycles of length \(n\) and a perfect matching joining the two cycles. Clearly each permutation graph \(X\) covers DB. If \(n\) is even, \(X\) is 3edgecolourable. If \(n\) is odd, there are infinitely many permutation graphs which are snarks. The least example is the Petersen graph. On the other hand, all known permutation snarks are of order \(2n\), where \(n\equiv 1 \mod 4\). Problem 1.ii: Are there permutation snarks of order \(2n\), where \(n\equiv 3 \mod 4\)? One can consider Problem 1.i for regular coverings. In particular, the following problem seems to be of interest. Problem 1.iii: Is there a snark regularly covering DB other then the Petersen graph? Let \(Q\) be a graph theoretical problem which asks for an assignment of objects of certain type to the vertices of an input graph, satisfying certain given rules. Representing the vertices by intervals and edges by nonempty intersections is a good example, as well as the wealth of graph coloring problems. Then RepExt(\(Q\)) is a variant whose input is a graph \(G\) and a partial assignment to some vertices, asking if this partial representation can be extended to an assignment to all vertices, satisfying the rules of \(Q\). SEFE(\(Q\)) is a variant whose input are several graphs \(G_1, G_2, \ldots, G_k\) such that the intersection of any two of them is their common subgraph \(Q\), and the question is if each of \(G_i\) allows a \(Q\)feasible assignment \(f_i\) such that all \(f_i\)'s coincide on the shared subgraph \(Q\). In most of the cases (but not all) when the complexities of both variants are known, SEFE(\(Q\)) is at least as difficult as RepExt(\(Q\)). Since both HCover and HPartialCover problems (see definitions below) are about assignments (of vertices of the parameter graph \(H\) to the vertices of the input graph \(G\)), we propose to study the RepExt and SEFE variants of them. The first candidates for investigation are the cases where the HCover (HPartialCover, respectively) problem is known to be solvable in polynomial time. Furthermore, the RepExt variant is a special case of another well studied variant, the List(\(Q\)) one (a partial assignment means that some lists are singletons  for the preassigned vertices  while the other lists are equal to the full domain). This raises a natural question if RepExt(HPartialCover) remains NPcomplete for some cases \(H\) for which List(HPartialCover) is known to be hard. Definition of the decision problems is as follows: References [1] Jan Kratochvil, Andrzej Proskurowski, Jan Arne Telle: Covering Regular Graphs. J. Comb. Theory, Ser. B 71(1): 116 (1997) [2] Jan Kratochvil, Andrzej Proskurowski, Jan Arne Telle: On the Complexity of Graph Covering Problems. Nord. J. Comput. 5(3): 173195 (1998) [3] Jiri Fiala, Jan Kratochvil: Complexity of Partial Covers of Graphs. ISAAC 2001: 537549 [4] Jiri Fiala, Jan Kratochvil: Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. WG 2006: 1526 [5] Jiri Fiala, Jan Kratochvil, Attila Por: On the computational complexity of partial covers of Theta graphs. Discrete Applied Mathematics 156(7): 11431149 (2008) [6] Bernard Lidicky, Marek Tesar: Complexity of Locally Injective Homomorphism to the Theta Graphs. IWOCA 2010: 326336 [7] Ondrej Bilka, Bernard Lidicky, Marek Tesar: Locally Injective Homomorphism to the Simple Weight Graphs. TAMC 2011: 471482 [8] Jan Kratochvil, Jan Arne Telle, Marek Tesar: Computational complexity of covering threevertex multigraphs. Theor. Comput. Sci. 609: 104117 (2016) For a fixed integer \(k \geq 1\), the \(k\)FoldCover problem takes as input two graphs \(G\) and \(H\) with \(V_G=kV_H\) and is to test whether there exists a locally bijective homomorphism from \(G\) to \(H\). Update: \(k\)FoldCover is NPcomplete for \(k=3\). This follows from the proof of Theorem 1(i) in S. Chaplick, J. Fiala, P. van 't Hof, D. Paulusma and M. Tesar. Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree. Theoretical Computer Science 590 (2015) 8695. In this proof, given an instance \((A,B)\) of 3Partition, two graphs \(G\) and \(H\) are constructed with the property that \(V_G=3V_H\) so that \((A,B)\) is a yesinstance if and only if there is a locally bijective homomorphism from \(G\) to \(H\). For \(k=2\), determining the computational complexity of \(k\)FoldCover is still open. The problem is to determine (hopefully matching) upper and lower bounds on the complexity of various covering problem; lower bounds under the assumption of Exponential Time Hypothesis. Special cases like planar input are also worth consideration. A dichotomy problem for signed graph homomorphisms P. Hell (with R. Brewster, F. Foucaud, and R. Naserasr) A signed graph \((G, \sigma)\) is a graph \(G\) together with a function \(\sigma : E(G) \to \{ +,  \}\). The sign of a cycle is the product of the signs of its edges. A switch at a vertex \(v\) changes \((G, \sigma)\) by changing the signs of all edges incident to \(v\). (Note that a switch does not change the sign of any cycle.) Two signed graphs \((G, \sigma)\) and \((G, \sigma')\) are equivalent if one can be obtained from the other by a sequence of switches. Zaslavsky has shown that two signed graphs are equivalent if and only if they have the same set of negative cycles. Let \((G, \sigma)\) and \((H, \pi)\) be signed graphs. A signed homomorphism of \((G, \sigma)\) to \((H, \pi)\) is a mapping \(f:V(G) \to V(H)\) such that for any \(uv \in E(G)\) we have \(f(u)f(v) \in E(H)\), and the two edges \(uv\) and \(f(u)f(v)\) have the same sign, after possibly replacing \((G, \sigma)\) by an equivalent signed graph \((G, \sigma')\). In other words, a signed homomorphism is required to preserve both the adjacencies and the signs of cycles. For any signed graph \((H,\pi)\), we consider the following signed homomorphism problem: INSTANCE: A signed graph \((G,\sigma)\) We ask: for which signed graphs \((H,\pi)\) is the problem solvable in polynomial time? A complexity classification is known when \((H,\pi)\) has no negative loop, and when \((H,\pi)\) has no positive loop, and when \((H,\pi)\) has no parallel edges of opposite signs. Two parallel edges of opposite signs can be viewed as a negative twocycle, i.e., a negative digon. A signed graph \((H,\pi)\) is a core if every signed homomorphism \(f\) of \((H,\pi)\) to \((H,\pi)\) is bijective. Every signed graph \((H,\pi)\) contains, as a subgraph, a unique (up to isomorphism and switching) core. Theorem 1 [1] Let \((H,\pi)\) be a connected signed graph that does not simultaneously contain a negative digon, a negative loop, and a positive loop. Then, the signed homomorphism problem for \((H,\pi)\) is polynomialtime solvable if the core of \((H,\pi)\) has at most two edges, and is NPcomplete otherwise. We believe that a full dichotomy holds for signed graph homomorphisms. In fact, we conjecture that all cases not covered in the theorem are NPcomplete. Conjecture 2 Let \((H,\pi)\) be a connected signed graph. Then the signed homomorphism problem for \((H,\pi)\) problem is polynomialtime solvable if the core of \((H,\pi)\) has at most two edges, and is NPcomplete otherwise. References [1] R. Brewster, F. Foucaud, P. Hell, and R. Naserasr. The complexity of signed graph and edgecoloured graph homomorphisms, Bordeaux Graph Workshop, 2016. [2] F. Foucaud and R. Naserasr. The complexity of homomorphisms of signed graphs and signed constraint satisfaction. Proceedings of the 11th Latin American Symposium on Theoretical Informatics 2014, LATIN 2014, Lecture Notes in Computer Science 8392:526537, 2014. [3] F. Harary. On the notion of balance of a signed graph. In Michigan Mathematical Journal 2(2):143146, 19531954. [4] P. Hell and J. Nesetril. On the complexity of \(H\)coloring. In Journal of Combinatorial Theory Series B 48(1), 92110, 1990. [5] R. Naserasr, E. Rollova, and E. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory 79(3):178212, 2015. [6] T. Zaslavsky. Characterizations of signed graphs. In Journal of Graph Theory 5(4):401406, 1981. [7] T. Zaslavsky. Signed graphs. In Discrete Applied Mathematics 4(1):4774, 1982. 

12301330 
Lunch  
13301500  Discussions  
15001530  Tea/Coffee  
16001700  Tour of Durham Castle (15 minute walk from the School)  
17001830  Welcome Reception in Palace Green Library, Deane Room 
Tuesday 10 January
09301030  Edita Máčajová 
Pointline Configurations and Conjectures in Graph Theory (show abstract) Slides 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 3edgecolouring. A configuration \(\mathcal{C}=(P,B)\) consists of a finite set \(P\) of points and a finite set \(B\) of blocks. Blocks are 3element 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 FanRaspaud Conjecture, problems concerting the perfect matching index of a graph and others. 
10301100  Tea/Coffee  
11001145  Marston Conder  Symmetric Cubic Graphs as Cayley Graphs (show abstract) Slides A graph \(\Gamma\) is symmetric if its automorphism group acts transitively on the arcs of \(\Gamma\), and \(s\)arctransitive if its automorphism group acts transitively on the set of \(s\)arcs of \(\Gamma\). Furthermore, if the latter action is sharplytransitive on \(s\)arcs, then \(\Gamma\) is \(s\)arcregular. It was shown by Tutte (1947, 1959) that every finite symmetric cubic graph is \(s\)arcregular for some \(s\leq 5\). Djokovic and Miller (1980) took this further by showing that there are seven types of arctransitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. The latter classification was refined by Conder and Nedela (2009), in terms of what types of arctransitive subgroup can occur in the automorphism group of \(\Gamma\). In this talk we consider the question of when a finite symmetric cubic graph can be a Cayley graph. We show that in five of the 17 ConderNedela classes, there is no Cayley graph, while in two others, every graph is a Cayley graph. In eight of the remaining ten classes, we give necessary conditions on the order of the graph for it to be Cayley; there is no such condition in the other two. Also we use covers (and the 'Macbeath trick') to show that in each of those last ten classes, there are infinitely many Cayley graphs, and infinitely many nonCayley graphs. This research grew out of some recent discussions with Klavdija Kutnar and Dragan Marusic. 
11451230  Barnaby Martin  The complexity of surjective homomorphism problems. (show abstract) Slides Classifying the complexity of surjective homomorphism problems seems to be a more challenging task than that for normal homomorphism problems. While \(H\)Colouring is wellunderstood for graphs \(H\), Surjective \(H\)Colouring is far from being classified. We survey known results about surjective homomorphism problems, with reference to the related Compaction and Retraction problems, look at recent work in the area, and ponder future directions for study. 
12301330  Lunch  
13301500  Discussions  
15001530  Tea/Coffee  
15301700  Discussions 
Wednesday 11 January
09301015  Martin Skoviera 
Cubic graphs that cannot be covered with four perfect matchings
(show abstract) Slides The celebrated BergeFulkerson conjecture suggests that every bridgeless cubic graph can have its edges covered with at most five perfect matchings. Since three perfect matchings suffice if and only if the graph in question is 3edgecolourable, uncolourable cubic graphs fall into two classes: those that can be covered with four perfect matchings, and those that require at least five. Cubic graphs that cannot be covered with four perfect matchings are extremely rare. Among the 64326024 snarks (uncolourable cyclically 4edgeconnected cubic graphs with girth at least five) on up to 36 vertices there are only two graphs that cannot be covered with four perfect matchings  the Petersen graph and a snark of order 34. In this talk we show that coverings with four perfect matchings can be described in terms of flows whose values lie in the configuration of six lines spanned by four points of the 3dimensional projective geometry \(PG(3,2)\) in general position. This characterisation provides us with a convenient tool for constructing new families of snarks that cannot be covered with four perfect matchings. One of our families includes all snarks currently known to require five perfect matchings to cover their edges. Another construction is based on regular covering projections using voltage graphs with voltages in \(\mathbb{Z}_5\). This is a joint work Edita Máčajová. 
10151100  Pavel Klavik  Graph Isomorphism Restricted by Lists (show abstract) Presentation The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs \(G\) and \(H\), it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NPcomplete: for each \(u \in V(G)\), we are given a list \({\mathfrak L}(u) \subseteq V(H)\) of possible images of \(u\). After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso. We prove the following:
Also, ListIso allows to classify results for the graph isomorphism problem. Some algorithms are robust and translate to ListIso. A fundamental problem is to construct a combinatorial polynomialtime algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NPhard for them, so no robust algorithm for cubic graph isomorphism exists, unless P \(=\) NP. 
11001130  Tea/Coffee  
Further discussions followed by departure for the excursion (exact timings to be confirmed). We will go together to Durham Railway Station (a scenic 20 minute riverside walk) and travel by train to Newcastle (less than 15 minutes). A visit to the Baltic Centre for Contemporary Art (free entry) is suggested though delegates might wish to consider other attractions in Newcastle. A packed lunch will be provided. Wikipedia provides a good overview of the Baltic. Their own website is more of a challenge. 
Thursday 12 January
09301030  Daniel Kráľ 
Subgraph Counts in Large Graphs (show abstract) Slides 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 3vertex graphs. The talk contains results based on a joint work with Roman Glebov, Andrzej Grzesik, Ping Hu, Tamás Hubai and Jan Volec. 
10301100  Tea/Coffee  
11001145  Thomas Bellitto  Complexity of locallyinjective homomorphisms to tournaments (show abstract) Slides This talk studies locallyinjective homomorphisms, also known as partial graph covers, between oriented graphs. Depending on the applications, several definitions of local injectivity exist in the literature that lead to subtly different problems. We study for each of them the complexity of the problem of determining the existence of a locallyinjective homomorphism from a graph to a given target tournament. The specific case where the target graph is a tournament is an important step toward more general results and already answers several related questions such as the complexity of oriented locallyinjective colouring. We find dichotomy theorems for the complexity of locallyinjective homomorphisms to reflexive tournaments, and report on progress towards such a theorem for locallyinjective homomorphisms to irreflexive tournaments. 
11451230  Peter Zeman  Automorphism groups of planar graphs (show abstract) Presentation In 1975, Babai characterized which abstract groups can be realized as the automorphism groups of planar graphs. In this paper, we give a more detailed and understandable description of these groups. We describe stabilizers of vertices in connected planar graphs as the class of groups closed under the direct product and semidirect products with symmetric, dihedral and cyclic groups. The automorphism group of a connected planar graph is then obtained as a semidirect product of a direct product of these stabilizers with a spherical group. Our approach translates into a quadratictime algorithm for computing the automorphism group of a planar graph which is the first such algorithm described in details. 
12301330  Lunch  
13301500  Discussions  
15001530  Tea/Coffee  
15301700  Discussions 
Friday 13 September
09301030  Discussions  
10301100 
Tea/Coffee  
11001230  Solved Problems!  
For those delegates still in Durham, rooms will be available in the School for the rest of the day and lunch will be provided 