Wednesday, September 13
09:00  10.00 Registration and coffee break
10:00 Workshop Openning
11:00  11:30 Coffee break
11:30  12:50 Session 1: Groups, permutations and graphs (Chair: Rita Zuazua)
13:15 Lunch 15:00  16:20 Session 2: Hamiltonicity and TSP (Chair: Ismael Gonzalez Yero)
16:50  17:30 Session 3: Functions on vertices and subgraphs (Chair: Ingo Schiermeyer)
Thursday, September 14
09:00  09:45 Invited talk: Ingo Schiermeyer
09:50  10:30 Session 4: Domination (Chair: Jerzy Topp)
10:30  11:00 Coffee break
11:00  12:00 Session 5: Miscellaneous (Chair: Jarosław Grytczuk)
12:30 Lunch and coffee break
14:00  19:00 Excursion (Gdynia sightseeing and visiting Emigration Museum) 19:30  23:00 Workshop dinner in Panorama Restaurant
Friday, September 15
09:00  09:45 Invited talk: Jarosław Grytczuk
09:50  10:10 Session 6: Ramsey numbers (Chair: Tomasz Dzido)
10:10  11:00 Coffee break
11:00  12:00 Session 7: Coloring (Chair: Marek Kubale)
Abstracts of invited talks
Abstract: The problems of detecting, finding, counting or listing subgraphs or induced subgraphs of a host graph that are isomorphic to a pattern graph are basic in graph algorithms. They are generally termed as subgraph isomorphism and induced subgraph isomorphism problems, respectively. Such wellknown NPhard problems as the independent set, clique, Hamiltonian cycle or Hamiltonian path can be regarded as their special cases.
Recent examples of applications of different variants of subgraph isomorphism include among other things: biomolecular networks, social networks, automatic design of processor systems, and network security. In the aforementioned applications, the pattern graphs are typically of fixed size which allows for polynomialtime bruteforce solutions. We present applications of three tools leading to more efficient algorithms for detecting and/or counting copies or induced copies of small pattern graphs in large host graphs. The first tool are fast algebraic algorithms for square and rectangular matrix multiplication. In particular, they yield an O(n^{ω}) time algorithm for detecting and counting triangles in a host graph on n vertices (Itai and Rodeh, 1978), where ω denotes the exponent of fast nxn matrix multiplication. Generally, for a pattern graph on k vertices and a host graph on n vertices, they yield O(n^{ω(⌊k/3⌋,⌈(k1)/3⌉,⌈k/3⌉)}) time solutions (Eisenbrand and Grandoni, 2004; Kloks, Kratsch, and Müller, 2000), where ω(p,q,r) denotes the exponent of fast matrix multiplication for rectangular matrices of size n^{p}xn^{q} and n^{q}xn^{r}, respectively. It is known that ω ≤ 2.373 (Le Gall, 2014; Vassilevska Williams, 2012) and for example ω(1,1,2) ≤ 3.257 (Le Gall, 2012). The second tool are equations in terms of the number of induced copies of kvertex pattern graphs in the host graph. Kloks et al. formulated such equations for k=4 that allowed them to conclude that if the number of induced copies is known for at least one of the pattern graphs on 4 vertices then the numbers for the remaining pattern graphs on 4 vertices can be computed relatively easily (Kloks, Kratsch, and Müller, 2000). Kowaluk et al. generalized the equations to include pattern graphs on more than four vertices (Kowaluk, Lingas, and Lundell, 2013). By using them they could improve upper bounds on detecting and counting copies of pattern graphs on k vertices different from the kclique (Kowaluk, Lingas, and Lundell, 2013). In particular, they showed that one can detect and count the number of copies of any pattern graph on 4 vertices different from K_{4} in O(n^{ω}) time. They also obtained an analogous upper bound for pattern graphs on 5 vertices different from K_{5}. The third tool is a probabilistic method for testing polynomials for identity with 0 (DeMillo and Lipton, 1978; Schwartz, 1980; Zippel, 1979). By using this method, Kowaluk et al. could derive faster randomized algorithms for the detection of induced copies of some pattern graphs on four and five vertices (Floderus, Kowaluk, A. Lingas, and Lundell, 2015). Finally, Vassilevska et al. could show that induced copies of all pattern graphs on 4 vertices different from K_{4} can be detected in O(n^{ω}) time with high probability (Vassilevska Williams, Wang, Williams, and Yu, 2015). They also derived an analogous randomized upper bound for some pattern graphs on five vertices.
Abstract: A graph G is called kcolourable, if its vertices can be coloured with k colours so that adjacent vertices obtain distinct colours. The smallest k such that a given graph G is kcolourable is called its chromatic number, denoted by χ(G). It is wellknown that ω(G) ≤ χ(G) ≤ Δ(G)+1 for any graph G, where ω(G) denotes its clique number and Δ(G) its maximum degree.
A family G of graphs is called χbound with binding function f if χ(G') ≤ f(ω(G')) holds whenever G∈G and G' is an induced subgraph of G. For a fixed graph H, let G(H) denote the family of graphs which are Hfree. Our work was motivated by the following problem posed by Gyárfás in 1985. Problem: What is the order of magnitude of the smallest χbinding function for G(2K_{2})? One of the earliest results is due to Wagon, who considered graphs without induced matchings. Theorem (Wagon, 1980) Let G be a 2K_{2}free graph with clique number ω(G). Then χ(G) ≤ ω(G)(ω(G)+1)/2.
In this talk we will show linear binding functions for several subclasses of (2K_{2},H)free graphs, where H∈{C_{4},Diamond,House,Gem,Paw}. We will also present binding functions for (2K_{2},Claw)free graphs. Finally, we will discuss extensions of our results to subclasses of P_{5}free graphs (Schiermeyer, 2016).
Abstract: A multigraph G is locally irregular if every pair of adjacent vertices have distinct degrees. The 123 conjecture states that every nontrivial simple graph can be made locally irregular by adding at most two edges between any pair of adjacent vertices (Karoński, Łuczak, and Thomason 2004). There exist many variations on this problem where one tries to get a locally irregular graph by other manipulations on vertex degrees. It turns out that one of possible variants is related to some deep number theoretic problems, like Graham's gcdproblem, Erdös Discrepancy Problem, or even the Riemann Hypothesis.
