Workshop programme

 Wednesday, September 13                                                                                                                                     

09:00 - 10.00  Registration and coffee break
10:00  Workshop Openning

10:15 - 11:00  Invited talk: Andrzej Lingas
11:00 - 11:30  Coffee break
11:30 - 12:50  Session 1: Groups, permutations and graphs (Chair: Rita Zuazua)
  • The zero sum partition of Abelian groups and its applications /Sylwia Cichacz-Przeniosło/
  • Cyclic automorphism groups of edge-colored graphs /Mariusz Grech/
  • Partial geometric difference sets and Cayley graphs /Semih Piri and Oktay Olmez/
  • Classification of labeled grids /Monika Rosicka/
12:55  Workshop photo

13:15 
Lunch

15:00 - 16:20  Session 2: Hamiltonicity and TSP (Chair: Ismael Gonzalez Yero)
  • Zhu condition for edge hamiltonian graphs /Grzegorz Gancarzewicz/
  • Hamiltonian prisms over some graphs under toughness conditions /Mou Gao/
  • On the generalized Redei-Camion theorem /Robert Malona/
  • Pareto-optimal algorithms for metric TSP /Ekaterina Beresneva/
16:20 - 16:50 Coffee break
16:50 - 17:30  Session 3: Functions on vertices and subgraphs (Chair: Ingo Schiermeyer)
  • Acyclic sum-list-partitions in graphs /Ewa Drgas-Burchardt and Agata Drzystek/
  • Bipartization of graphs /Mateusz Miotk, Jerzy Topp, and Paweł Żyliński/
 
 Thursday, September 14                                                                                                                                         

09:00 - 09:45  Invited talk: Ingo Schiermeyer
09:50 - 10:30  Session 4: Domination (Chair: Jerzy Topp)
  • On some relationships between independence and domination in graphs /Ismael Gonzalez Yero/
  • On the super domination number of lexicographic product graphs
    /Magda Dettlaff, Magdalena Lemańska, Juan Alberto Rodríguez-Velázquez, and Rita Zuazua/       
10:30 - 11:00  Coffee break
11:00 - 12:00  Session 5: Miscellaneous (Chair: Jarosław Grytczuk)
  • The mixed Chinese postman problem /Mariia Gordenko/ 
  • From rooks to matchings, via marriages /Adam Morawiec/
  • Orthogonal one-factorizations of complete multipartite graphs
    /Mariusz Meszka and Magdalena Tyniec-Motyka/        
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)
  • On lower bound of induced Ramsey numbers /Izolda Gorgol/ 
10:10 - 11:00  Coffee break
11:00 - 12:00  Session 7: Coloring (Chair: Marek Kubale)
  • Majority coloring games /Bartłomiej Bosek, Gabriel Jakóbczak, and Jarosław Grytczuk/ 
  • The dichromatic number of some circulant digraphs /Nahid Javier and Bernardo Llano/
  • Colorings of R2 avoiding patterns on lines            /Michał Debski, Jarosław Grytczuk, Urszula Pastwa,      
    Barbara Pilat, Joanna Sokół, Michał Tuczynski, Przemysław Wenus, and Krzysztof Wesek/       
12:30  Lunch, coffee, tee, and cheesecake (Closing Workshop)

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 well-known NP-hard 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: bio-molecular 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 polynomial-time brute-force 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⌋,⌈(k-1)/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 npxnq and nqxnr, 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 k-vertex 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 k-clique (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 K4 in O(nω) time. They also obtained an analogous upper bound for pattern graphs on 5 vertices different from K5.
    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 K4 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 k-colourable, 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 k-colourable is called its chromatic number, denoted by χ(G). It is well-known 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 H-free. 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(2K2)?

    One of the earliest results is due to Wagon, who considered graphs without induced matchings.

Theorem
(Wagon, 1980) Let G be a 2K2-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 (2K2,H)-free graphs, where H∈{C4,Diamond,House,Gem,Paw}. We will also present binding functions for (2K2,Claw)-free graphs. Finally, we will discuss extensions of our results to subclasses of P5-free graphs (Schiermeyer, 2016).
 
 

Abstract: A multigraph G is locally irregular if every pair of adjacent vertices have distinct degrees. The 1-2-3 conjecture states that every non-trivial 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 gcd-problem, Erdös Discrepancy Problem, or even the Riemann Hypothesis.