Skip to main content

Schedule

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.

Information booklet (pdf)

show/hide all abstracts

Monday 9 January

0900-0930Registration
0930-0935Welcome to Durham
0935-1030Pavol HellObstruction Certificates for Geometrically Defined Graph (and Digraph) Classes
(hide 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 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.
1030-1100Tea/Coffee
1100-1230Open Problems show/hide all texts
Problem 1: Snarks, problemauthor(hide text)
It can be easily seen that given covering X→YX→Y between graphs, a nowhere-zero kk-flow defined on YY lifts to a nowhere-zero kk-flow of XX. In particular, if both XX and YY are cubic graphs we get: if YY is 3-edge-colourable, then XX is 3-edge-colourable as well. A general problem reads as follows:Problem 1.i: Characterise non-3-edge-colourable cubic graphs covering the dumbell graph DB, a 2-vertex 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 nn and a perfect matching joining the two cycles. Clearly each permutation graph XX covers DB. If nn is even, XX is 3-edge-colourable. If nn 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 2n2n, where n≡1mod4n≡1mod4.Problem 1.ii: Are there permutation snarks of order 2n2n, where n≡3mod4n≡3mod4?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?Problem 2: Extending Partial Assignments, problemauthor(hide text)
Let QQ 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 non-empty intersections is a good example, as well as the wealth of graph coloring problems. Then RepExt(QQ) is a variant whose input is a graph GG 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 QQ. SEFE(QQ) is a variant whose input are several graphs G1,G2,…,GkG1,G2,…,Gk such that the intersection of any two of them is their common subgraph QQ, and the question is if each of GiGi allows a QQ-feasible assignment fifi such that all fifi’s coincide on the shared subgraph QQ. In most of the cases (but not all) when the complexities of both variants are known, SEFE(QQ) is at least as difficult as RepExt(QQ).Since both H-Cover and H-Partial-Cover problems (see definitions below) are about assignments (of vertices of the parameter graph HH to the vertices of the input graph GG), we propose to study the RepExt and SEFE variants of them. The first candidates for investigation are the cases where the H-Cover (H-Partial-Cover, 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(QQ) 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(H-Partial-Cover) remains NP-complete for some cases HH for which List(H-Partial-Cover) is known to be hard.Definition of the decision problems is as follows:
H-Cover asks if an input graph GG allows a locally bijective homomorphism onto the parameter graoh HH, i.e., if GG covers HH (in the topological sense).
H-Partial-Cover asks if GG allows a locally injective homomorphism into HH, i.e, if GG is an induced subgraph of a cover of HH.References[1] Jan Kratochvil, Andrzej Proskurowski, Jan Arne Telle: Covering Regular Graphs. J. Comb. Theory, Ser. B 71(1): 1-16 (1997)[2] Jan Kratochvil, Andrzej Proskurowski, Jan Arne Telle: On the Complexity of Graph Covering Problems. Nord. J. Comput. 5(3): 173-195 (1998)[3] Jiri Fiala, Jan Kratochvil: Complexity of Partial Covers of Graphs. ISAAC 2001: 537-549[4] Jiri Fiala, Jan Kratochvil: Locally Injective Graph Homomorphism: Lists Guarantee Dichotomy. WG 2006: 15-26[5] Jiri Fiala, Jan Kratochvil, Attila Por: On the computational complexity of partial covers of Theta graphs. Discrete Applied Mathematics 156(7): 1143-1149 (2008)[6] Bernard Lidicky, Marek Tesar: Complexity of Locally Injective Homomorphism to the Theta Graphs. IWOCA 2010: 326-336[7] Ondrej Bilka, Bernard Lidicky, Marek Tesar: Locally Injective Homomorphism to the Simple Weight Graphs. TAMC 2011: 471-482[8] Jan Kratochvil, Jan Arne Telle, Marek Tesar: Computational complexity of covering three-vertex multigraphs. Theor. Comput. Sci. 609: 104-117 (2016)Problem 3: Regular Covers, problemauthor(hide text)
For a fixed integer k≥1k≥1, the kk-FoldCover problem takes as input two graphs GG and HH with |VG|=k|VH||VG|=k|VH| and is to test whether there exists a locally bijective homomorphism from GG to HH.Update: kk-FoldCover is NP-complete for k=3k=3. This follows from the proof of Theorem 1(i) inS. 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) 86-95.In this proof, given an instance (A,B)(A,B) of 3-Partition, two graphs GG and HH are constructed with the property that |VG|=3|VH||VG|=3|VH| so that (A,B)(A,B) is a yes-instance if and only if there is a locally bijective homomorphism from GG to HH.For k=2k=2, determining the computational complexity of kk-FoldCover is still open.Problem 4: Complexity of Covering, problemauthor(hide text)
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.Problem 5: Signed Graph Homomorphisms, problemauthor(hide text)
A dichotomy problem for signed graph homomorphismsP. Hell (with R. Brewster, F. Foucaud, and R. Naserasr)A signed graph (G,σ)(G,σ) is a graph GG together with a function σ:E(G)→{+,−}σ:E(G)→{+,−}. The sign of a cycle is the product of the signs of its edges. A switch at a vertex vv changes (G,σ)(G,σ) by changing the signs of all edges incident to vv. (Note that a switch does not change the sign of any cycle.) Two signed graphs (G,σ)(G,σ) and (G,σ′)(G,σ′) 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,σ)(G,σ) and (H,π)(H,π) be signed graphs. A signed homomorphism of (G,σ)(G,σ) to (H,π)(H,π) is a mapping f:V(G)→V(H)f:V(G)→V(H) such that for any uv∈E(G)uv∈E(G) we have f(u)f(v)∈E(H)f(u)f(v)∈E(H), and the two edges uvuv and f(u)f(v)f(u)f(v) have the same sign, after possibly replacing (G,σ)(G,σ) by an equivalent signed graph (G,σ′)(G,σ′). In other words, a signed homomorphism is required to preserve both the adjacencies and the signs of cycles.For any signed graph (H,π)(H,π), we consider the following signed homomorphism problem:INSTANCE: A signed graph (G,σ)(G,σ)
QUESTION: Does (G,σ)(G,σ) admit a signed homomorphism to (H,π)(H,π)?We ask: for which signed graphs (H,π)(H,π) is the problem solvable in polynomial time?A complexity classification is known when (H,π)(H,π) has no negative loop, and when (H,π)(H,π) has no positive loop, and when (H,π)(H,π) has no parallel edges of opposite signs. Two parallel edges of opposite signs can be viewed as a negative two-cycle, i.e., a negative digon.A signed graph (H,π)(H,π) is a core if every signed homomorphism ff of (H,π)(H,π) to (H,π)(H,π) is bijective. Every signed graph (H,π)(H,π) contains, as a subgraph, a unique (up to isomorphism and switching) core.Theorem 1 [1] Let (H,π)(H,π) 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,π)(H,π) is polynomial-time solvable if the core of (H,π)(H,π) has at most two edges, and is NP-complete 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 NP-complete.Conjecture 2 Let (H,π)(H,π) be a connected signed graph. Then the signed homomorphism problem for (H,π)(H,π) problem is polynomial-time solvable if the core of (H,π)(H,π) has at most two edges, and is NP-complete otherwise.References[1] R. Brewster, F. Foucaud, P. Hell, and R. Naserasr. The complexity of signed graph and edge-coloured 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:526–537, 2014.[3] F. Harary. On the notion of balance of a signed graph. In Michigan Mathematical Journal 2(2):143–146, 1953-1954.[4] P. Hell and J. Nesetril. On the complexity of HH-coloring. In Journal of Combinatorial Theory Series B 48(1), 92–110, 1990.[5] R. Naserasr, E. Rollova, and E. Sopena. Homomorphisms of signed graphs. Journal of Graph Theory 79(3):178–212, 2015.[6] T. Zaslavsky. Characterizations of signed graphs. In Journal of Graph Theory 5(4):401–406, 1981.[7] T. Zaslavsky. Signed graphs. In Discrete Applied Mathematics 4(1):47–74, 1982.
1230-1330Lunch
1330-1500Discussions
1500-1530Tea/Coffee
1600-1700Tour of Durham Castle (15 minute walk from the School)
1700-1830Welcome Reception in Palace Green Library, Deane Room

Tuesday 10 January

0930-1030Edita MáčajováPoint-line Configurations and Conjectures in Graph Theory
(hide 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 3-edge-colouring.A configuration C=(P,B)C=(P,B) consists of a finite set PP of points and a finite set BB of blocks. Blocks are 3-element subsets of PP such that for each pair of points of PP there is at most one block in BB which contains both of them.A colouring of a cubic graph GG with a configuration C=(P,B)C=(P,B) is an assignment of an element from PP to each edge of GG such that the three points that meet at any vertex form a block of BB.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.
1030-1100Tea/Coffee
1100-1145Marston ConderSymmetric Cubic Graphs as Cayley Graphs
(hide abstract) Slides
A graph ΓΓ is symmetric if its automorphism group acts transitively on the arcs of ΓΓ, and ss-arc-transitive if its automorphism group acts transitively on the set of ss-arcs of ΓΓ. Furthermore, if the latter action is sharply-transitive on ss-arcs, then ΓΓ is ss-arc-regular.It was shown by Tutte (1947, 1959) that every finite symmetric cubic graph is ss-arc-regular for some s≤5s≤5. Djokovic and Miller (1980) took this further by showing that there are seven types of arc-transitive 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 arc-transitive subgroup can occur in the automorphism group of ΓΓ.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 Conder-Nedela 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 non-Cayley graphs.This research grew out of some recent discussions with Klavdija Kutnar and Dragan Marusic.
1145-1230Barnaby MartinThe complexity of surjective homomorphism problems.
(hide abstract) Slides
Classifying the complexity of surjective homomorphism problems seems to be a more challenging task than that for normal homomorphism problems. While HH-Colouring is well-understood for graphs HH, Surjective HH-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.
1230-1330Lunch
1330-1500Discussions
1500-1530Tea/Coffee
1530-1700Discussions

Wednesday 11 January

0930-1015Martin SkovieraCubic graphs that cannot be covered with four perfect matchings
(hide abstract) Slides
The celebrated Berge-Fulkerson 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 3-edge-colourable, 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 4-edge-connected 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 3-dimensional projective geometry PG(3,2)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 Z5Z5.This is a joint work Edita Máčajová.
1015-1100Pavel KlavikGraph Isomorphism Restricted by Lists
(hide abstract) Presentation
The complexity of graph isomorphism (GraphIso) is a famous unresolved problem in theoretical computer science. For graphs GG and HH, it asks whether they are the same up to a relabeling of vertices. In 1981, Lubiw proved that list restricted graph isomorphism (ListIso) is NP-complete: for each u∈V(G)u∈V(G), we are given a list L(u)⊆V(H)L(u)⊆V(H) of possible images of uu. After 35 years, we revive the study of this problem and consider which results for GraphIso translate to ListIso.We prove the following:When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso.Combinatorial algorithms for GraphIso translate into algorithms for ListIso: for trees, planar graphs, interval graphs, circle graphs, permutation graphs, bounded genus graphs, and bounded treewidth graphs.Algorithms based on group theory do not translate: ListIso remains NP-complete for cubic colored graphs with sizes of color classes bounded by 8.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 polynomial-time algorithm for cubic graph isomorphism, avoiding group theory. By the 3rd result, ListIso is NP-hard for them, so no robust algorithm for cubic graph isomorphism exists, unless P == NP.
1100-1130Tea/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

0930-1030Daniel KráľSubgraph Counts in Large Graphs
(hide 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 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.
1030-1100Tea/Coffee
1100-1145Thomas BellittoComplexity of locally-injective homomorphisms to tournaments
(hide abstract) Slides
This talk studies locally-injective 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 locally-injective 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 locally-injective colouring. We find dichotomy theorems for the complexity of locally-injective homomorphisms to reflexive tournaments, and report on progress towards such a theorem for locally-injective homomorphisms to irreflexive tournaments.
1145-1230Peter ZemanAutomorphism groups of planar graphs
(hide 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 quadratic-time algorithm for computing the automorphism group of a planar graph which is the first such algorithm described in details.
1230-1330Lunch
1330-1500Discussions
1500-1530Tea/Coffee
1530-1700Discussions

Friday 13 September

0930-1030Discussions
1030-1100Tea/Coffee
1100-1230Solved 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