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-0930

Registration
0930-0935 Welcome to Durham
0935-1030 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 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-1100 Tea/Coffee
1100-1230 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 nowhere-zero \(k\)-flow defined on \(Y\) lifts to a nowhere-zero \(k\)-flow of \(X\). In particular, if both \(X\) and \(Y\) are cubic graphs we get: if \(Y\) is 3-edge-colourable, then \(X\) 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 \(n\) and a perfect matching joining the two cycles. Clearly each permutation graph \(X\) covers DB. If \(n\) is even, \(X\) is 3-edge-colourable. 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?

Problem 2: Extending Partial Assignments, problem, author, text

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 non-empty 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 H-Cover and H-Partial-Cover 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 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(\(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(H-Partial-Cover) remains NP-complete for some cases \(H\) 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 \(G\) allows a locally bijective homomorphism onto the parameter graoh \(H\), i.e., if \(G\) covers \(H\) (in the topological sense).
H-Partial-Cover asks if \(G\) allows a locally injective homomorphism into \(H\), i.e, if \(G\) is an induced subgraph of a cover of \(H\).


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, problem, author, text

For a fixed integer \(k \geq 1\), the \(k\)-FoldCover problem takes as input two graphs \(G\) and \(H\) with \(|V_G|=k|V_H|\) and is to test whether there exists a locally bijective homomorphism from \(G\) to \(H\).

Update: \(k\)-FoldCover is NP-complete 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) 86-95.

In this proof, given an instance \((A,B)\) of 3-Partition, two graphs \(G\) and \(H\) are constructed with the property that \(|V_G|=3|V_H|\) so that \((A,B)\) is a yes-instance 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.

Problem 4: Complexity of Covering, problem, author, 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, problem, author, text

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)\)
QUESTION: Does \((G,\sigma)\) admit a signed homomorphism to \((H,\pi)\)?

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 two-cycle, 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 polynomial-time solvable if the core of \((H,\pi)\) 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,\pi)\) be a connected signed graph. Then the signed homomorphism problem for \((H,\pi)\) problem is polynomial-time solvable if the core of \((H,\pi)\) 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 \(H\)-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-1330

Lunch
1330-1500 Discussions
1500-1530 Tea/Coffee
1600-1700 Tour of Durham Castle (15 minute walk from the School)
1700-1830 Welcome Reception in Palace Green Library, Deane Room

Tuesday 10 January

0930-1030 Edita Máčajová Point-line 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 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.

1030-1100 Tea/Coffee
1100-1145 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\)-arc-transitive if its automorphism group acts transitively on the set of \(s\)-arcs of \(\Gamma\). Furthermore, if the latter action is sharply-transitive on \(s\)-arcs, then \(\Gamma\) is \(s\)-arc-regular.

It was shown by Tutte (1947, 1959) that every finite symmetric cubic graph is \(s\)-arc-regular for some \(s\leq 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 \(\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 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-1230 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 well-understood 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.

1230-1330 Lunch
1330-1500 Discussions
1500-1530 Tea/Coffee
1530-1700 Discussions

Wednesday 11 January

0930-1015 Martin Skoviera Cubic graphs that cannot be covered with four perfect matchings
(show 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)\) 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á.

1015-1100 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 NP-complete: 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:

  1. When GraphIso is GI-complete for a class of graphs, it translates into NP-completeness of ListIso.
  2. 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.
  3. 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-1130 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

0930-1030 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 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-1100 Tea/Coffee
1100-1145 Thomas Bellitto Complexity of locally-injective homomorphisms to tournaments
(show 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-1230 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 quadratic-time algorithm for computing the automorphism group of a planar graph which is the first such algorithm described in details.

1230-1330 Lunch
1330-1500 Discussions
1500-1530 Tea/Coffee
1530-1700 Discussions

Friday 13 September

0930-1030
Discussions
1030-1100

Tea/Coffee
1100-1230 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