• Bratislavský seminár z teórie grafov

The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While $3$-edge-colourable graphs have defect~$0$, those that cannot be $3$-edge-coloured have defect at least $3$. We show that every bridgeless cubic graph with defect $3$ can have its edges covered with at most five perfect matchings, which verifies a long-standing conjecture of Berge for this class of graphs. Moreover, we determine the extremal graphs.
This is a joint work with Ján Katabáš, Edita Máčajová, and Roman Nedela.

♦ ♦ ♦

A generalized quadrangle of order $q$ is an incidence structure such that on every line there are exactly $q+1$ points, at every point there intersect exactly $q+1$ lines, and no two distinct points lay on the two distinct lines. A spread in a generalized quadrangle is a set of lines which partition the point set. Generalized quadrangles play important role in various parts of mathematics, for example, their incidence graphs are Moore graphs of girth $8$.
In 2003 Kharabani and Thorabi showed that for any prime power $q$ there exists a system of $q+1$ generalized quadrangles of order $q$ on the same set of points sharing a common spread such each pair of points lies on a line in at least one of the generalized quadrangles. They called such system a geometric Siamase color graph of order $q$.
Klin, Reichard and Woldar showed that lines of generalized quadrangles in a geometric Siamese color graph of order $q$ form a Steiner system with parameters $(2,q+1,q^3+q^2+q+1)$ and they used this observation to classify geometric Siamese color graphs of order $2$. Later they found hundreds of geometric Siamese color graph order $3$.
Using algebraic properties of generalized quadrangles with a spread derived by Brouwer in $1984$ we completely classify geometric Siamese color graphs of order $2$ and $3$.

♦ ♦ ♦

A skew morphism of a finite group $A$ is a permutation $\varphi$ on $A$ fixing the identity element, and for which there exists an integer-valued function $\pi$ on $A$ such that $\varphi(xy)=\varphi(x)\varphi^{\pi(x)}(y)$ for all $x,y\in A$. If $\pi$ is constant on the orbits of $\varphi$, the skew morphism $\varphi$ is called smooth. The theory of skew morphisms is a crucial algebraic tool to investigate symmetric embeddings of graphs into orientable surfaces. In this talk, we will present the most recent progress in the classification problem of skew morphisms of cyclic groups, and show that a cyclic group of order $n$ underlies only smooth skew morphisms if and only if $n=2^en_1$, where $0\leq e\leq 4$ and $n_1$ is a square-free odd number.

♦ ♦ ♦

We enumerate orientably regular maps of any given type with automorphism group isomorphic to a twisted linear fractional group; these groups form the ‘other’ family in Zassenhaus’ classification of finite sharply 3-transitive groups.
This is a joint work with S. Pavliková and J. Širáň.

♦ ♦ ♦

Barnette's conjecture states that every cubic planar bipartite 3-connected graph is Hamiltonian. Only partial results are known. One approach is to study subgraphs (multipoles) known as reducible configurations. We say that multipole G is reducible to multipole R if every Hamiltonian cycle which passes through R can be extended into G. We present new cubic planar bipartite reducible configurations found with computer search. In addition, we present new infinite class of reducible configurations and prove reducibility to their respective reductors.
This is a joint work with František Kardoš.

♦ ♦ ♦

We examine the relationship between two measures of uncolourability of cubic graphs -- their resistance and flow resistance. The resistance of a cubic graph G, denoted by r(G), is the minimum number of edges whose removal results in a 3-edge-colourable graph. The flow resistance of G, denoted by r_f(G), is the minimum number of zeroes in a 4-flow on G. Fiol et al. (2018) made a conjecture that r_f(G) never exceeds r(G). We disprove this conjecture by presenting a family of cubic graphs G_n with resistance n and flow resistance 2n. We also present another family H_n where resistance is 2 and flow resistance is n, demonstrating that the ratio r_f(G)/r(G) can be arbitrarily large. Members of both families are nontrivial snarks.
The talk is based on joint results with Imran Allie (University of Cape Town) and Edita Mačajová.

♦ ♦ ♦

A graph A is called stronger than a graph B if every simple graph that covers A also covers B. This notion was defined and found useful for NP-hardness reductions for disconnected graphs. Kratochvil conjectured that if $A$ has no semi-edges, then $A$ is stronger than $B$ if and only if $A$ covers $B$. We prove this conjecture for cubic one-vertex graphs, and we also justify it for all cubic graphs $A$ with at most 4 vertices.
(Joint work with J. Kratochvil)

♦ ♦ ♦

Godsil's 1985 paper on inverting trees initiated investigation of inverting arbitrary graphs. We will give an introduction into this topic, motivated by open questions in determination of the spectral gap of a graph, which is the difference between the smallest positive and the largest negative eigenvalue.
(Joint work with Daniel Sevcovic a Jozef Siran)

♦ ♦ ♦

Let G be a bridgeless cubic graph. The Berge-Fulkerson Conjecture (1970s) states that G admits a list of six perfect matchings such that each edge of G belongs to exactly two of these perfect matchings. If answered in the affirmative, two other recent conjectures would also be true: the Fan-Raspaud Conjecture (1994), which states that G admits three perfect matchings such that every edge of G belongs to at most two of them; and a conjecture by Mazzuoccolo (2013), which states that G admits two perfect matchings whose deletion yields a bipartite subgraph of G. It can be shown that given an arbitrary perfect matching of G, it is not always possible to extend it to a list of three or six perfect matchings satisfying the statements of the Fan-Raspaud and the Berge-Fulkerson conjectures, respectively. In this talk, we show that given any 1+-factor F (a spanning subgraph of G such that its vertices have degree at least 1) and an arbitrary edge e of G, there always exists a perfect matching M of G containing e such that G∖(F∪M) is bipartite. Our result implies Mazzuoccolo's conjecture, but not only. It also implies that given any collection of disjoint odd circuits in G, there exists a perfect matching of G containing at least one edge of each circuit in this collection.
This is a joint work with Edita Máčajová and Jean Paul Zerafa.

♦ ♦ ♦

Given an orientable map M, and an integer e relatively prime to the valency of M, the e-th rotational power M^e of M is the map formed by replacing the cyclic rotation of edges around each vertex with its e-th power. If maps M and M^e are isomorphic, and the corresponding isomorphism preserves the orientation of the carrier surface, then we say that e is an exponent of M.
In this talk, I will recall and explain some useful definitions, and then show how canonical regular covers of maps can be used to prove that for every given hyperbolic pair (k,m) there exists an orientably-regular map of type {m,k} with no non-trivial exponents. In particular, for each hyperbolic pair (k,m) we find a suitable orientable map of type {m,k} such that the canonical regular cover of this map is an orientably-regular map (of the same type) with no non-trivial exponents.
This is joint work with Veronika Bachratá.

♦ ♦ ♦

In 2010, M. Conder, T. Tucker and the presenter published a classification of orientably-regular maps of genus $p+1$ for primes $p > 13$, with a computer-free proof for $p > 83$; for primes $p$ in the range $17 \le p \le 83$ part of the argument relied on computational results of M. Conder. Classification of such maps for $p\le 7$ was available by earlier results going back to 1930s -- 1980s, however, in a number of cases without explicit proofs.
In the talk we will give an outline of methods and results leading to a computer-free classification of orientably-regular maps of genus $p+1$ for all primes $p\le 83$ (and hence for all primes $p$). This is a report on a joint work with M. Bachraty, M. Conder and J. Siagiova.

♦ ♦ ♦

A graph is half-arc-transitive if it is transitive on the vertices and edges, but not on the arcs (directed edges). It is well known that a finite half-arc-transitive has an even valency greater or equal to 4. Somewhat surprisingly, all constructions of 4-valent half-arc-transitive graphs known to date have bounded girth. This led Primož Šparl ask whether there exist 4-valent half-arc-transitive graphs of arbitrarily large girth. We answer this question in the affirmative.
This is a joint work with Jozef Širáň.

♦ ♦ ♦

The famous cage problem asks for finding a smallest k-regular graph with girth g (that is, the length of a shortest cycle) also called a (k,g)-cage. As our main result, we prove that every (3,13)-cage is cyclically 13-edge-connected, that is, it contains no set of fewer than 13 edges that separates two cycles. Note that all 3-regular cages are known up to girth 12 and each of them has its cyclic edge-connectivity equal to its girth. The girth 13 is thus the smallest girth for which the exact order of a cage is not known (it lies between 202 and 272).
Our main idea consists of extending the cubic case of the cage problem to subcubic graphs: we ask for a smallest graph with a finite girth at least g, exactly l vertices of degree 2 and all the remaining vertices of degree 3. We develop techniques for approaching this problem and present our results in small cases. Also, we will discuss possible generalisations of our results and relation to the problem whether each cycle separating g-edge-cut in a (3, g)-cage separates a cycle. We believe our results will shed some new light on the cage problem and perhaps lead to some improvements in exhaustive computer searches. This is a joint work with Edita Máčajová.

♦ ♦ ♦

The degree-diameter problem is to determine the largest number of vertices in a graph with a given degree and diameter. There is a restricted version of this problem which asks for the largest vertex transitive graph with prescribed parameters. McKay, Miller and Širáň used voltage graphs to construct a family of graphs of diameter 2, degree (3q-r)/2 and order 2*q^2, where q is a prime power congruent to r mod 4 and r is -1, 0 or 1. McKay-Miller-Širáň are vertex transitive for r=1 while for the other two values of r they are highly symmetric but not vertex transitive.
Later Šiagiová found a simpler voltage graph construction for the vertex transitive McKay-Miller-Širáň graphs, using base graphs with just two vertices - dipoles. Also, Hafner described all three families geometrically by using incidence graphs of finite affine planes.
We present the results of Šiagiová and Hafner and use them to show that all McKay-Miller-Širáň graphs can be constructed as lifts of dipoles.

♦ ♦ ♦

Destroying all cycles of a graph by removing as few vertices as possible is an extensively studied problem in graph theory and computer science. The minimum number of vertices whose deletion eliminates all cycles of a graph is its decycling number. In this talk we deal with the problem of determining the decycling number of a cubic graph. We show that the problem is closely related to determining the largest genus of an orientable surface into which the graph can be cellularly embedded. Using this relationship we prove that every cyclically 4-connected cubic graph G has a minimum decycling set S such that G-S is connected (that is, a tree) and S itself is either independent or induces a subgraph with exactly one edge. This improves a classical result of Payan and Sakarovitch (1975). We conjecture that such a decycling set exist in almost all cubic graphs.
This is a joint work with Roman Nedela and Michaela Seifrtova.

♦ ♦ ♦

A vertex-transitive closure of a graph G is a vertex-transitive supergraph of G on the same vertex set. The vertex-transitive number of G is the smallest possible degree of a vertex-transitive closure of G.
In this talk, we introduce the concepts of vertex-transitive closure and vertex-transitive number of a graph. We estimate and in some cases also determine vertex-transitive numbers for graphs with relatively simple structure and we prove some general observations.

♦ ♦ ♦

An r-balanced flow is an assignment b of values to the vertices of G, an orientation O, and an assignment \phi of values to the edges of G such that 1. b(v) = deg(v) (mod 2), for each vertex v, 2. 0 <= \phi(e) <= (r-2)/r, for each edge e, 3. \sum_{e \in O^+} \phi(e) - \sum_{e \in O^-} \phi(e) = b(v), for each vertex v.
We show that this concept coincides with the concept of balanced valuations introduced by Jaeger and thus it coincides with circular nowhere-zero r-flows. This definition gives a practical approach to compute the circular flow number for graphs on up to approximately $100$ vertices using the state of the art ILP solvers. We discuss how similar ideas could be used for the dual concept of circular colourings of certain graphs.

♦ ♦ ♦

♦ ♦ ♦

For an integer k>=1 and a graph G, let K_k(G) be the graph that has vertex set all proper k-colorings of G, and an edge between two vertices x and y whenever the coloring y can be obtained from x by a single Kempe change. A theorem of Meyniel from 1978 states that K_5(G) is connected, with diameter O(5^|V(G)|), for every planar graph G. We significantly strengthen this result, by showing that there is a positive constant c such that K_5(G) has diameter O(|V(G)|^c) for every planar graph G.
This is a joint work with Quentin Deschamps, Carl Feghali, Clément Legrand-Duchesne, and Théo Pierron.

♦ ♦ ♦

The problem of finding $(k,g)$-cages, that is, finding the smallest (in terms of the number of vertices) $k$-regular graphs of girth $g$ is largely open. One of the approaches of finding small graphs with given properties are lifting constructions. In this talk we examine our constructions of small $k$-regular graphs of girth 6 and 8, obtained by lifting dipoles and achieving the order of existing graphs of the corresponding girth. We also discuss another construction based on groups, called $G$-graphs, and show under which circumstances the $G$-graphs can be obtained as lifts of dipoles.
This work is joint with Š. Gyürki, J. Šiagiová and J. Širáň.

♦ ♦ ♦

A d-dimensional nowhere-zero r-flow on a graph G, an (r,d)-NZF for short, is a flow where the value on each edge is an element of R^d whose norm lies in the interval [1,r-1]. Such a notion is a natural generalization of the well-known concept of circular nowhere-zero r-flow (i.e. d = 1). In this paper, we mainly consider the parameter \phi_d(G), which is the minimum of the real numbers r such that G admits an (r,d)-NZF. For every bridgeless graph G. The 5-flow Conjecture claims that \phi_1(G) <= 5, while a conjecture by Kamal Jain suggests that \phi_d(G)=1, for all d >= 3. Here, we address the problem of finding a possible upper-bound in the case d = 2. We show that, for all bridgeless graphs, \phi_2(G) <= 1 + \sqrt{5} and that the oriented 5-Cycle Double Cover Conjecture implies \phi_2(G) <= \Phi^2, where \Phi is the Golden Ratio. Moreover, we discuss some connections between this problem and some other well-known conjectures. Finally, we focus our attention on the cubic case: we propose a geometric method to describe an (r,2)-NZF of a cubic graph in a compact way, and we apply it in some instances.

♦ ♦ ♦

We prove that there exists a non-trivial snark with circular chromatic index $r$ for any rational $r\in (3, 3+1/3]$. In addition, for each integer $g$ there exists an $\eps$ such that each rational $r\in (3,3+\eps)$ is a circular chromatic index of a cyclically $5$-edge-connected snark of girth at least $g$. We also construct cyclically $6$-edge-connected snarks for every rational number in $(3, 3+\eps)$, for some constant $\eps$.
This is a joint work with Jan Mazák.

♦ ♦ ♦

A bi-coset graph is a bipartite graph with its two partite sets consisting of the cosets of two subgroups of a given group G, and the adjacency determined by non-empty intersection. Bi-coset graphs constitute a classical object of algebraic graph theory and have been studied in various contexts (often with regard to their symmetries).
In our talk, bi-coset graphs are revisited with the aim of using them in connection with the Cage Problem - the problem of finding a smallest k-regular graph of girth g - and its generalization - the problem of finding a smallest biregular graph of girth g with the vertices of degrees m,n. The girth of a bi-coset graph is shown to be related to the existence of special alternating sequences of elements from H and K, and k-regular bi-coset graphs of arbitrary large girths are shown to exist for all k >= 2. Bi-coset graphs are shown to be particularly suitable for constructions of bipartite biregular graphs which are biregular graphs in which each of the two sets making the graph bipartite consists of vertices of the same degree.
A few bipartite biregular bi-coset graphs constructed by this method can be shown to be of the smallest order among all bipartite biregular graphs with the same parameters. Interestingly, one of such constructions starts from prime pairs of the form p, 6p+1.
The results discussed in this talk come from a joint paper with S. Gyurki, J. Siran and Y. Wang. This is the first of a series of two talks on the topic, with the second talk delivered by S. Gyurki.

♦ ♦ ♦

Edge colorings of cubic graphs by configurations provide a common language for the study of various open problems about cubic graphs (Fan-Raspaud conjecture, Berge-Fulkerson conjecture, 5-cycle double cover conjecture, etc). In this language we present several observations and ask questions which seem to be outside focus of experts working on these problems.

♦ ♦ ♦

Edge-elimination is an operation of removing an edge together with its end-vertices. We study the effect of this operation on the cyclic connectivity of a cubic graph. Disregarding a small number of cubic graphs with no more than six vertices, this operation cannot decrease cyclic connectivity by more than two. We show that apart from three exceptional graphs (the cube, the twisted cube, and the Petersen graph) every 2-connected cubic graph on at least eight vertices contains an edge whose elimination decreases cyclic connectivity by at most one. A substantial ingredient of the proof is a theorem that provides a structural characterisation of Isaacs flower snarks and their natural generalisation, twisted Isaacs graphs.
We explain how the result is related to several other problems concerning cubic graphs, for example, the existence of long cycles, decycling, and maximum genus embeddings of cubic graphs into surfaces. This is a joint work with Roman Nedela.

♦ ♦ ♦

♦ ♦ ♦

The Hadwiger conjecture is one of the most famous and widely open conjecture in graph coloring. It states that a graph with no K_t-minor admits a (k-1)-coloring. In this talk we will consider a reconfiguration version of the problem. One can transform a proper coloring of a graph into another proper coloring by applying a Kempe change: ie switching the two colors of a maximal bichromatic component. Two colorings are called equivalent if there exists a sequence of Kempe changes to apply to transform the first coloring into the second.
In 1981, Las Vergnas and Meyniel conjectured a reconfiguration analog of the Hadwiger conjecture: if a graph has no K_t minor, then all its k-colorings are equivalent. We disprove this conjecture, more precisely, we prove that for any epsilon, there exists t large enough such that there exists a graph with no K_t minor, that has two ((3/2-epsilon)*t)-colorings which are not equivalent.
This is joint work with Marthe Bonamy, Clément Legrand-Duchesne, and Marc Heinrich.

♦ ♦ ♦

In this talk we examine the following question. Let G be a cyclically k-edge-connected cubic graph with a k-edge-cut separating a cyclic component C different from the k-cycle. How can we complete C to a cyclically k-edge-connected cubic graph H? Our work extends the results of Andersen et al. from 1988 who studied this problem for the case k = 4, and our recent results for the case k = 5. We show that if the resulting graph H has girth at least k and H – C is cyclic and different from the k-cycle, then H is cyclically k-edge-connected. Based on this result we provide an algorithm determining whether a given graph C can be a subgraph of some cyclically k-edge-connected cubic graph. Moreover, for k = 6 we show that each such component C can be completed to a cyclically 6-edge-connected cubic graph by adding 8 additional vertices forming two 6-cycles that share a path of length three.
This is a joint work with Edita Máčajová.

♦ ♦ ♦

Expander graphs are highly connected sparse finite graphs with many applications in extremal graph theory, networks, error-correcting codes, derandomization, number theory, and group theory. The aim of the talk is to survey some of the best known methods for constructing expander graphs and the constructions that will be discussed are probabilistic, combinatorial (graph theoretic) and algebraic (both group theoretic and spectral). The last part of the presentation will be devoted to covering graph constructions and their potential for constructing expander families.

♦ ♦ ♦

The energy of a graph G, E(G), is the sum of absolute values of the eigenvalues of its adjacency matrix. This concept was first introduced by Gutman in 1978. In this talk, we try to present some lower and upper bounds for the energy of graphs and present their structural and spectral properties and also present some open conjectures in this area.

♦ ♦ ♦

♦ ♦ ♦

We prove that planar graphs of maximum degree 3 and of girth at least 7 are 3-edge-colorable, extending the previous result for girth at least 8 by Kronk, Radlowski, and Franen from 1974.
This is a joint work with Sebastien Bonduelle.
https://arxiv.org/abs/2108.06115

♦ ♦ ♦

A circular nowhere-zero r-flow on a bridgeless graph G is an orientation of the edges and an assignment of real values from [1, r-1] to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number of G is the infimum over all values $r$ such that $G$ admits a nowhere-zero $r$-flow. We prove that the circular flow number of Goldberg snark G_{2k+1} is 4+1/(k+1), proving a conjecture of Goedgebeur, Mattiolo, and Mazzuoccolo [J. Goedgebeur, D. Mattiolo, G. Mazzuoccolo: \emph{Computational results and new bounds for the circular flow number of snarks}, Discrete Mathematics 343 (2020), 112026.].
Besides this, we discuss computational aspects of circular flows. We describe an efficient way how to reformulate the problem of determining the circular flow number as a mixed linear programing problem. We review computational results obtained by this approach.

♦ ♦ ♦

The Cage Problem - the problem of finding a smallest k-regular graph of girth g, i.e., the (k,g)-cage - is well known to be very hard and the exact orders of cages are known for very few parameter pairs (k,g). One possible approach to understanding structural properties of cages includes considering biregular graphs that contain vertices of two degrees, m and n, and generalizing the Cage Problem by looking for smallest graphs of girth g containing vertices of the two degrees m and n, the (m,n;g)-cages. In the case of odd girths, results of this approach differ quite a bit from the regular Cage Problem as the orders of biregular (m,n;g)-cages are determined for all odd girths g and degree pairs m,n in which m is considerably smaller than n. The even girth case is still wide open, and has been therefore restricted to bipartite biregular graphs in which the two bipartite sets consist exclusively of vertices of one of the degrees (regular cages of even girth are also conjectured to be bipartite). We survey the most resent results on biregular and bipartite biregular cages, present some improved lower bounds, and discuss an interesting connection between bipartite biregular cages and t-designs.

♦ ♦ ♦

♦ ♦ ♦

Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components G_1 and G_2. We prove that each component G_i can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless G_i is a cycle of length five.
Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1998. Our results enable us to use inductive arguments in the class of the cubic graphs with cyclic connectivity 5. Also, this inductive approach can be used in computer-assisted constructions of cubic graphs with cyclic connectivity 5 and other prescribed properties such as large girth or oddness. This is a joint work with Edita Máčajová.

♦ ♦ ♦

Let $b(n)$ denote the smallest integer $b$ such that each red-blue edge coloring of the complete bipartite graph $K_{b,b}$ contains a red $C_4$ or blue $K_{1,n}$. This variation of the Ramsey problem was studied by Carnielli, Goncalves and Monte Carmelo (2000, 2008). They obtained the upper bound b(n) <= n + [sqrt(n)], and provided constructions that prove this bound sharp in infinitely many cases. They also posed two conjectures about $b(n)$. We give further constructions that give equality in this bound, and refute both conjectures. The results rely on projective planes, some Zarankiewicz numbers and the non-existence of certain nearly generalized polygons.
This work is joint with Imre Hatala and Sam Mattheus.

♦ ♦ ♦

An independent transversal in a graph G with a given partition P of its vertex set is an independent set in G intersecting each block of P in a single vertex. Given a lower bound on the size of blocks of P, which conditions on the degrees in G imply the existence of an independent transversal? We will discuss topological and probabilistic aspects of this classical problem as well as recent developments related to the entropy compression method. Includes joint work with Carla Groenland, Matt Wales and Oscar Treffers.

♦ ♦ ♦

♦ ♦ ♦

We investigate automorphism groups of planar graphs. The main result is a complete recursive description of all abstract groups that can be realized as automorphism groups of planar graphs. The characterization is formulated in terms of inhomogeneous wreath products. In the proof, we combine techniques from combinatorics, group theory, and geometry. This significantly improves the Babai's description (1975).

♦ ♦ ♦

The weight w(e) of an edge is the degree-sum of its end-vertices. In 1955, Kotzig proved that every 3-connected plane graph contains an edge of weight at most 13. Later, Borodin proved the existence of such an edge in plane graphs with minimum degree at least three. If we consider a graph embedded on a surface with non-positive Euler characteristic, minimum degree three and sufficiently large number of vertices, then the existence of an edge of weight at most 15 can be proved. In the talk we describe types of edges in connected graphs with minimum degree at least 2, minimum face size at least 3 and sufficiently large number of vertices embedded on a surface with non-positive Euler characteristic. We will also discuss the quality of our results.
Joint work with K. Cekanova and R. Sotak.

♦ ♦ ♦

Graph decompositions, graceful labelings, perfect difference sets - all these are well established topics in Graph Theory or in Number Theory. They have a surprising and nice application in memory distribution of a parallel numerical solution of a large system of equations with dense matrices, which arise e.g. when using Boundary Element Method.
In this talk we present a brief overview of the classical results and explain the method, that allowed us to solve larger problems than traditional parallelization would allow. We have successfully used cyclic graph decompositions when solving systems with millions of variables.
Prezentácia

♦ ♦ ♦

Symmetry-preserving operations on polyhedra have been studied for a very long time. However, it was only recently that a general description of all 'local symmetry-preserving operations' (lsp-operations) was presented. With this description it becomes possible to prove general results about all lsp-operations instead of studying every operation separately. We use this approach to investigate the effect of lsp-operations on the (3-)connectivity of embedded graphs.
Historically, symmetry-preserving operations have mostly been applied to polyhedra (3-connected plane graphs), but there is no mathematical reason why the new definition of lsp-operations could not be applied to more general embedded graphs. For plane graphs, all lsp-operations preserve 3-connectivity, but once we start looking at graphs with a higher genus this is no longer the case. The dual is the most striking example of an lsp-operation that can greatly reduce the connectivity of an embedded graph, but there are other operations that can destroy 3-connectivity in certain embedded graphs. We characterise exactly which lsp-operations always preserve 3-connectivity and which operations do not.
Prezentácia

♦ ♦ ♦

The aim of this talk is to introduce Terwilliger algebra of a graph. We will first define Terwilliger algebra of an arbitrary connected simple graph, and its (irreducible) modules. We will show that in the context of Terwilliger algebras, distance-(bi)regular graphs arise quite naturally. We will be interested in the interplay between certain combinatorial properties of graphs and the module structure of the associated Terwilliger algebras

♦ ♦ ♦

The irregularity strength of a graph G, s(G), is the least k admitting a [k]-weighting of the edges of G assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of G via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant C such that s(G) is at most n/d+C for each d-regular graph G with n vertices and d at least 2. However, the best published result thus far implies an upper bound 6n/d+C. We shall show that the conjecture of Faudree and Lehel holds asymptotically in the cases when d is neither very small nor very close to n.

♦ ♦ ♦

In his 1965 seminal paper on edge coloring, Vizing proved that a (Delta+1)-edge coloring can be reached from any given proper edge coloring through a series of Kempe changes, where Delta is the maximum degree of the graph. He concludes the paper with the following question: can an optimal edge coloring be reached from any given proper edge coloring through a series of Kempe changes? In other words, if the graph is Delta-edge-colorable, can we always reach a Delta-edge-coloring? We discuss a key ingredient in Vizing's original paper, namely the use of fans; we show how to extend the notion and answer his question in the affirmative for all triangle-free graphs.
This is a joint work with M. Bonamy, O. Defrain, T. Klimosova, and A. Lagoutte.

♦ ♦ ♦

Nanotubical graphs are obtained by wrapping a hexagonal grid, and then possibly closing the tube with caps. We derive asymptotics for several distance-based generalized chemical indices which are of the form $$ I^{\lambda}(G)=\sum_{u\ne v}f(u,v)dist^{\lambda}(u,v), $$ where $\lambda$ is a real number and $f(u,v)$ is a nonnegative symmetric function which is non-decreasing and which depends only on degrees of $u$ and $v$. All our results are obtained using double integrating and they show that the leading term depends on the circumference of the nanotube and not on its particular type.
This is a joint work with Vesna Andova and Riste Skrekovski

♦ ♦ ♦

Macajova, Raspaud and Skoviera defined the chromatic number of a signed graph which coincides for all-positive signed graphs with the chromatic number of unsigned graphs. They conjectured that in this setting, for signed planar graphs four colors are always enough, thereby generalising The Four Color Theorem. We disprove the conjecture.

♦ ♦ ♦

A k-edge-coloring of a graph G is an assignment of colors {1,...,k} to edges of G, such that adjacent edges receive different colors. If α is an edge-coloring of G, then for a vertex v of G, let S_α(v) be the set of colors that edges incident to v receive. If G is a cubic graph, then a normal k-edge-coloring of G is a k-edge-coloring with the property that for any edge uv |S_α(u) ∪ S_α(v)| ≠ 4. The normal chromatic index of a cubic graph (denoted by γ′_N(G)) is the smallest k, for which G admits a normal k-edge-coloring. Jaeger conjectured in 1985 that all bridgeless cubic graphs have normal chromatic index at most five. Even if the original conjecture of Jaeger is for bridgeless cubic graphs, we can define the normal chromatic index for any simple cubic graph. We show that γ′_N(G) ≤ 7 for any simple cubic graph G, and this bound is best-possible. Moreover, we discuss other possible approximation results, where we insist to use exactly five colours but we admit to have some "abnormal" edges.
This is a joint work with Vahan Mkrtchyan.
Prezentácia

♦ ♦ ♦

A proper edge colouring of a graph is strong if it creates no bichromatic path of length three. It is well known that for a strong edge colouring of a k-regular graph at least 2k-1 colors are needed. We show that a k-regular graph admits a strong edge couloring with 2k-1 colors if and only if it covers the Kneser graph K(2k-1,k-1). In particular, a cubic graph is strongly 5-edge-colorable whenever it covers the Petersen graph.
One of the implications of this result is that a conjecture about strong edge colourings of subcubic graphs proposed by Faudree et al. [Ars Combin. 29 B (1990), 205--211] is false.
This is a joint work with Borut Lužar, Edita Máčajová and Roman Soták.

♦ ♦ ♦

Thomassen (1995) showed that every planar graph of girth at least 5 is 3-choosable (i.e., can be properly colored from any assignment of lists of at least 3 allowed colors at each vertex). However, it has been open whether this statement can be proven via reducible configurations and discharging (such an argument would be easier to generalize to coloring graphs embedded on other surfaces). We find such a proof: we show that each planar graph of girth at least 5 and minimum degree at least 3 contains a small subgraph H such that each vertex of H has at most one neighbor outside of H (an island), and we find an unavoidable set of islands which are reducible using the polynomial method of Alon and Tarsi. We also consider analogous questions for planar graphs in general, without the girth condition.
This is a joint work with Marthe Bonamy, Michelle Delcourt, Zdeněk Dvořák, and Luke Postle.

♦ ♦ ♦

Let $G$ be a cyclically $4$-connected cubic graph with a cycle separating $4$-edge-cut $S$ and let $H$ be one component of $G - S$. We give the necessary and sufficient condition under which the component $H$ can be extended to a cyclically $4$-connected cubic graph of the same order by adding two edges. Our work completes the result of Goedgebeur, Máčajová and Škoviera, who showed that the component $H$ can be extended to a cyclically $4$-connected cubic graph by adding two adjacent vertices and restoring $3$-regularity. These results provide useful induction methods for cyclically $4$-connected cubic graphs.
This is a joint work with Edita Máčajová. The same results were also published by Andersen, Fleischner and Jackson.

♦ ♦ ♦

The aim of the talk is to generalize properties satisfied by highly symmetric (vertex-, edge- or arc-transitive) graphs to larger classes of graphs and to look for families of graphs that share some of the properties of symmetric graphs but are not themselves symmetric.
One such class is the class of edge-girth-regular $egr(v,k,g,\lambda)$-graphs which are $k$-regular graphs of order $v$ and girth $g$ in which every edge is contained in $\lambda$ distinct $g$-cycles. Beside the obvious edge-transitive graphs, examples include other important classes of graphs such as Moore graphs, as well as many of extremal $k$-regular graphs of prescribed girth or diameter. Infinitely many $egr(v,k,g,\lambda)$-graphs are known to exist for sufficiently large parameters $(k,g,\lambda)$, and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters $(k,g,\lambda)$.
We derive lower bounds in terms of the parameters $k,g$ and $\lambda$. We also determine the orders of the smallest $egr(v,k,g,\lambda)$-graphs for some specific parameters $(k,g,\lambda)$, and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.
Joint work with A. Zavrtanik Drglin, S. Filipovski, and T. Raiman.

♦ ♦ ♦

Existence of a regular, self-dual and self-Petrie-dual map of any given even valency was established by Archdeacon, Conder and the presenter in 2014. In the talk we will give details about an extension of this result to odd valencies greater than 3 (joint work with O. Jeans and J. Fraser).

♦ ♦ ♦

A binary snark is a cubic graph which cannot be properly 3-edge-coloured and is spanned by the balanced cubic tree T_d of depth d for some d. A binary snark G is called a rotation snark if an automorphism of T_d that cyclically permutes the edges incident with the root of T_d extends to an automorphism of G. One motivation for the study of rotation snarks comes from the intention to find small snarks of girth 7 and even cyclically 7-connected snarks. So far, only very few binary snarks have been found (one of them being the Petersen graph), mostly as a result of an extensive computer search. We present a construction of infinitely many rotation snarks with cyclic connectivity 5.
This is a joint work with Edita Macajova.

♦ ♦ ♦

In ths talk we will discuss the beginnings of the seminar, reasons for the establishment of the seminar, and the reasons for the emigration of prof. Rosa and prof. Kotzig.

♦ ♦ ♦

Biró, Hujter, and Tuza (1992) introduced the concept of H-graphs, intersection graphs of connected subregions of a graph H thought of as a one-dimensional topological space. They relate to and generalize many important classes of geometric intersection graphs, e.g., interval graphs, circular-arc graphs, split graphs, and chordal graphs.
Surprisingly, we negatively answer a 30-year-old question of Biró, Hujter, and Tuza which asks whether H-graphs can be recognized in polynomial time, for a fixed graph H. Moreover, our paper opens a new research area in the field of geometric intersection graphs by studying H-graphs from the point of view of fundamental computational problems of theoretical computer science: recognition, graph isomorphism, dominating set, clique, and colorability.
(joint work with: Steven Chaplick, Martin Töpfer, Jan Voborník)

♦ ♦ ♦

♦ ♦ ♦

We show that the circular flow number of a cubic graph can be determined in time O(1.94^n). The running time can be improved to O(1.5^n) if we do not need to distinguish the circular flow number values between 5 and 6. Finally, we observe that it is possible to decide the flow number of a cubic graph in O(1.26^n) time. We discuss how the results transfer to circular colourings.

♦ ♦ ♦

Critical snarks are non-3-edge-colourable cubic graphs such that the removal of any two adjacent vertices leaves a 3-edge-colourable graph. A vast majority of them is also bicritical -- i.e. removing any two vertices leaves a colourable graph. Therefore, critical snarks that are not bicritical form a rather interesting class of snarks -- they are called strictly critical snarks and were studied by Chladný and Škoviera along with their relation to bicriticality of cyclically 4-connected snarks. Inspired by the analysis of small cases, we construct an infinite family of strictly critical snarks with girth 6. Furthermore, by proving that a certain type of superposition preserves criticality, we construct an infinite class of cyclically 6-connected strictly critical snarks, which solves a problem proposed by Chladný and Škoviera.

♦ ♦ ♦

We recall that a tournament is a directed graph having precisely one arc between each pair of its nodes. Following Chung and Graham (1991), we say that a tournament T is quasirandom if for every X ⊆ V(T),
∑_{v ∈ X}| d⁺(v;X) - d^-(v;X) = o(n²)
(in fact, they provided a number of equivalent definitions of quasirandomness of tournaments). We say that a tournament F is quasirandom-forcing if the following is satisfied for every tournament T. If the density of F in T is the same as the expected density of F in a random tournament, then T is quasi-random. We recall that a tournament is transitive if it contains no directed cycle. Coregliano and Razborov (2017) showed that every transitive tournament on at least 4 nodes is quasirandom-forcing (see also exercise 10.44(b) in Lovász (1993)). For completeness, we recall that no tournament on 3 nodes is quasirandom-forcing (it follows, for instance, from the result of Goodman (1959)). Regarding non-transitive tournaments on n nodes, it is known that none is quasirandom-forcing for n = 4, and Coregliano, Parente and Sato (2019) showed that there is one for n = 5 (and the combination of their results and the result of Hancock, Kráľ, Skerman and Volec (2019+) gives that it is the only one for n = 5), and Bucić, Long, Shapira and Sudakov (2019+) observed that there is none for n ≥ 7. We close the remaining case by showing that there is none for n = 6.
This is a joint work with Robert Hancock, Dan Kráľ, Taísa Martins, Roberto Parente, Fiona Skerman and Jan Volec.

♦ ♦ ♦

Let $G$ be a bridgeless graph and let $cc(G)$ denote the length of a shortest cycle cover of $G$. The best known result for the general case, $cc(G) \leq {5 \over 3}|E(G)|$ $(\approx 1.6667|E(G)|)$, was established over 35 years ago. Recently, Fan proved that $cc(G) < 1.6258|E(G)|$ for graphs with minimum degree at least 3 (loops being allowed) and $cc(G) < 1.6148|E(G)|$ for loopless graphs with minimum degree at least 3. We improve his first result by proving that $cc(G) < 1.0741|S| + 1.6148|E(G)-S|$ where $S$ denotes the set of loops of a graph $G$. This implies that if $G$ has minimum degree at least 3, then $cc(G) < 1.6148|E(G)|$.
This is a joint work with Robert Lukoťka.

♦ ♦ ♦

In 1994, it was conjectured by Fan and Raspaud that every simple bridgeless cubic graph has three perfect matchings whose intersection is empty. In this talk we solve a problem recently proposed by Mkrtchyan and Vardanyan by giving an equivalent formulation of the Fan-Raspaud Conjecture. We also study a possibly weaker conjecture which states that in every simple bridgeless cubic graph there exist two perfect matchings such that the complement of their union is a bipartite graph. We here show that this conjecture can be equivalently stated using $H$-colourings, we prove it for graphs having oddness at most four and extend it to bridgeless cubic multigraphs and certain cubic graphs having bridges. Other related conjectures and their connection to the above will also be discussed.
This is a joint work with Giuseppe Mazzuoccolo.

♦ ♦ ♦

The shortest cycle cover conjecture suggests that every bridgeless cubic can have its edges covered with a collection of cycles of total length not exceeding (7/5).m where m is the number of edges. The covering ratio 7/5 is best possible, being reached by the Petersen graph. However, all cyclically 4-connected cubic graphs where the length of a shortest cycle cover is known have covering ratio close to the natural lower bound which equals 4/3. In line with this observation, Brinkmannn et al. (JCTB, 2013) made a conjecture that every cyclically 4-connected cubic graph has a cycle cover of length at most (4/3)m+o(m). We disprove this conjecture by exhibiting an infinite family of cyclically 4-connected cubic graphs whose shortest cycle cover has length at least (4/3 + 1/69)m.

♦ ♦ ♦

One of the most classical themes in extremal graph theory is the study of the interplay of subgraph densities. We will present two results that belong to this theme. The first concerns the following conjecture of Lovasz: any finite feasible set of subgraph density constraints can be extended to a finite set such that the asymptotic structure of graphs satisfying the constraints is unique. We will disprove the conjecture.
The second result is inspired by the Erdos-Rademacher Problem on the minimum possible triangle density in a graph with a given edge density. A conjecture of Linial and Morgenstern which asserts that, among all tournaments with a given density d of cycles of length three, the density of cycles of length four is minimized by tournaments with a structure analogous to that of graphs appearing in the Erdos-Rademacher Problem. We prove this conjecture for d>=1/36 using methods from spectral graph theory, and demonstrate that the structure of extremal examples is more complex than expected by giving its full description for d>=1/16.
The talk is based on results obtained in joint work with Timothy Chan, Andrzej Grzesik, Laszlo Miklos Lovasz and Jonathan Noel.

♦ ♦ ♦

Reed and Wood, and independently Norine, Seymour, Thomas, and Wollan, showed that for each $t$ there is $c(t)$ such that every graph on $n$ vertices with no $K_t$ minor has at most $c(t)n$ cliques. Wood asked in 2007 if $c(t) < c^t$ for some absolute constant $c$. This problem was recently solved by Lee and Oum. In this paper, we determine the exponential constant. We prove that every graph on $n$ vertices with no $K_t$ minor has at most $3^{2t/3+o(t)}n$ cliques. This bound is tight for $n \geq 4t/3$. The method and result can generalize to any minor-closed family of graphs.
We use the similar idea to give an upper bound on the number of cliques in an $n$-vertex graph with no $K_t$-subdivsion. Easy computation will give an upper bound of $2^{3t+o(t)}n$; a more careful examination gives an upper bound of $2^{1.48t+o(t)}n$. We conjecture that the optimal exponential constant is $3^{2/3}$ as in the case of minors.
This is a joint work with Jacob Fox.

♦ ♦ ♦

A sequence r₁, r₂,...,r_2n such that r_i = r_n+i for all 1 ≤ i ≤ n, is called a repetition. A sequence S is called nonrepetitive if no subsequence of consecutive terms of S forms a repetition.
In 1906 Norwegian mathematician Axel Thue started a systematic study of word structure. In his seminal paper he showed that there are arbitrarily long nonrepetitive sequences over three symbols. Since then Thue's non- repetitive sequences have repetitively occurred also in mathematics and various questions concerning nonrepetitive colourings of graphs have been formulated.
Alon at al. introduced a natural generalization of Thue's sequences for colouring of graphs. An edge-colouring / vertex-colouring of a graph G is nonrepetitive if the sequence of colours on any path in G is nonrepetitive. A natural question is whether there is a finite bound for the number of colours needed to colour the edges / vertices of G in such a way, that the colours of no path of G form a repetition.
There are several ways how to relax the requirements in this problem and several kinds of so called problems of Thue's type. Hence, many graph colouring parameters of Thue's type: the Thue chromatic number and index, the Thue choice number and index, the facial Thue chromatic number and index, the facial Thue choice number and index, the strong and weak total Thue chromatic number, the total Thue choice number, have been defined. All of these are connected with colourings of graphs that omit repetitions. Here you come familiar with some of them.

♦ ♦ ♦

The metric dimension of a (di)graph $G$ is the minimum cardinality of a subset $R$ (resolving set) of vertices of $G$ such that all vertices of $G$ are uniquely determined by their distances to (or from) the vertices of $R$. In this talk we deal with metric dimension of 2-generated Cayley digraphs of split metacyclic groups. We show some interesting results for general metacyclic groups. For some special parameters we give exact values of metric dimension.

♦ ♦ ♦

If a graph with non-zero edge labels has a non-singular adjacency matrix, then one may use the inverse matrix to define a (labeled) graph that may be considered to be the inverse graph to the original one. It has been known that an adjacency matrix of a labeled tree is non-singular if and only if the tree has a unique perfect matching. In the opposite case one may use a generalized inverse (which, in the symmetric case, coincides with Moore-Penrose, Drazin, or group inverse) of the adjacency matrix to 'invert' a tree. A formula for entries of such a generalized inverse of a tree follows from the work of Britz, Olesky and van den Driessche (2004), based on a general formula for determining the Moore-Penrose inverse.
In our talk we will briefly introduce various approaches to 'inverting' non-invertible matrices, state a formula for a generalized inverse of (an adjacency matrix of) a labeled tree, and outline principles leading to a new proof of validity of this formula (based solely on considering eigenvectors).
This is a joint work with Jozef Širáň.

♦ ♦ ♦

The Wiener index (the distance) of a graph is the sum of distances between all pairs of vertices. We study the maximum possible value of this invariant among graphs on $n$ vertices with fixed number of blocks $p$. It is known that among graphs on $n$ vertices that have just one block, the $n$-cycle has the largest Wiener index. And the $n$-path, which has $n-1$ blocks, has the maximum Wiener index in the class of graphs on $n$ vertices. We show that among all graphs on $n$ vertices which have $p\ge 2$ blocks, the maximum Wiener index is attained by a graph composed of two cycles joined by a path (here we admit that one or both cycles can be replaced by a single edge, as in the case $p=n-1$ for example). Finally, for each $n$ and $p$ we specify the lengths of the cycles in the extremal graph.
This is a joint work with S. Bessy, F. Dross, M. Knor and R. Skrekovski.

♦ ♦ ♦

A unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face $\alpha$ the maximal color appears exactly once on the vertices of $\alpha$. Fabrici and Göring proved that six colors are enough for any plane graph and conjectured that four colors suffice. Thus, this conjecture is a strengthening of the Four Color Theorem. Wendland later decreased the upper bound from six to five.
We first show that the conjecture holds for various subclasses of planar graphs but then we disprove it for planar graphs in general. So, we conclude that the facial unique-maximum chromatic number of the sphere is not four but five.
Joint work with Vesna Andova, Bernard Lidicky, Borut Luzar, and Kacy Messerschmidt.

♦ ♦ ♦

A color digraph is a complete digraph in which every dart is assigned a color. Color digraphs are an important tool in various areas, e.g., combinatorics, group theory, sports, and others.
Association schemes and coherent configurations form special classes of color (di)graphs, with significant applications in graph theory, group theory, statistics, coding theory ...
The Weisfeiler-Leman stabilization is a polynomial time algorithm which, given a color graph $S$, provides the smallest coherent configuration $S'$ such that each color class of $S$ is union of classes of $S'$.
In this talk we recall basic properties of association schemes and coherent configurations and we present the Weisfeiler-Leman stabilization.

♦ ♦ ♦

THe oddness of a bridgeless cubic graph $G$ is the minimal number of odd circuits in a $2$-factor of $G$. The weak oddness of $G$ is the minimal number of odd components in an even factor of $G$. The resistance of $G$ is the minimal number of vertices that have to be deleted in order to get a $3$-edge-colourable graph from $G$.
As the first result we show that there exist graphs with weak oddness $4$, resistance $4$, and arbitrarily large oddness [I. Allie: Oddness to resistance ratios in cubic graphs, Discrete Mathematics 342 (2019), 387 392].
Second, we show how to decide $3$-edge-colourability, determine the oddness, the weak oddness, and the resistance of a $n$ vertex cubic graph $G$ in time ${\cal O}^*(3^{(1/6+\varepsilon)\cdot n})$. [Joint work with a group of people from KAMAK problem solving seminar].
Third, we show that that if a cubic graph has nowhere-zero $A$-flow (where $A$ is an abelian group) or $k$-flow then it has also a nowhere-zero $A$-flow or $k$-flow where the edges incident with one vertex have their flow values and orientations prescribed (subject to obvious necessary conditions) [M. DeVos: Flows on Bidirected Graphs, arXiv:1310.8406; Y. Lu, R. Luo, C.-Q. Zhang: Multiple weak $2$-linkage and its applications on integer flows of signed graphs, European Journal of Combinatorics 69 (2018), 36 48].

♦ ♦ ♦

For a simple graph $G=(V,E)$, the Wiener index is defined as the sum of distances between all pairs of vertices, i.e. $W(G)=\sum_{\{u, v\} \subseteq V(G)} d(u,v)$. The Szeged index is defined as $\Sz(G)= \sum_{e=ij \in E}n_{e}(i)\cdot n_{e}(j)$, where $n_{e}(i)$ is the number of vertices strictly closer to $i$ than $j$, and analogously, $n_{e}(j)$ is the number of vertices strictly closer to $j$. A well-know inequality between the Szeged and Wiener indices says that $\Sz(G)=\sum_{e=ij\in E(G)} n_e(i)n_e(j) \ge \sum_{\left\{u,v\right\}} d(u,v)= W(G)$ for every graph~$G$. In the past, variable variations of the standard topological indices were defined. Following this line, we study a natural generalisation of the above inequality, namely $\sum_{e=ij\in E(G)} (n_e(i)n_e(j))^\alpha \ge \sum_{\left\{u,v\right\}} d(u,v)^\alpha$. We show that for all trees the inequality is true if $\alpha>1$, and the opposite inequality holds if $0\le \alpha<1$. In fact, the first result also holds for bipartite graphs and for graphs on $n$ vertices with at most $n+3$ edges, but the opposite one does not. For general graphs we solve also the case $\alpha<0$ and we present interesting conjectures. Observe, that both the sums are interesting on their own, and in accordance with the usual terminology they can be called the variable Szeged and variable Wiener indices.
This is a joint work with Martin Knor and Riste Škrekovski.

♦ ♦ ♦

Let $G$ be a graph. By the $k,l$-antiradius of $G$, $p_{k,l}(G)$, we mean the value $$\max_{K\subseteq V(G)}\{\min_{L\subseteq L}\{d_l(L);\,|L|=l\}; |K|=k\},$$ where by $d_l(L)$ we mean the sum of distances between all pairs of vertices in $L$.This parameter is in a way dual to radius and we focus on $l=2$, i.e., we consider the $k,2$-anti-radius. We give a tight upper bound for $k,2$-anti-radius over the class of connected graphs on $n$ vertices. Such a bound states, how large the smallest distance among $k$ distinct vertices in an $n$-vertex graph can be. Also, we solve the corresponding problem for 2-connected graphs for $k=3$.

♦ ♦ ♦

We discuss a new family of cubic graphs, which we call SGP-graphs, that bears a close resemblance to the family of generalized Petersen graphs, both in definition and properties. The focus of our presentation is on determining the algebraic properties of graphs from our new family. We look for highly symmetric graphs, e.g., graphs with large automorphism groups, vertex- or arc-transitive graphs. In particular, we present arithmetic conditions for the defining parameters that guarantee that graphs with these parameters are vertex-transitive or Cayley, and we find one arc-transitive SGP-graph which is not a generalized Petersen graph.

♦ ♦ ♦

A signed graph $(G,\sigma)$ is a graph $G$ with a signature $\sigma \colon E \to \{1,-1\}$. The flow number $\Phi(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the smallest integer $k$, for which there exists an integer nowhere-zero $k$-flow on $(G,\sigma)$. The circular flow number $\Phi_c(G,\sigma)$ of a flow-admissible signed graph $(G,\sigma)$ is the infimum of real numbers $r$ for which there exists an $\mathbb{R}$-flow on $(G,\sigma)$ satisfying that absolute values of all the flow values are in the interval $[1,r-1]$.
The relationship between the flow number $\Phi(G)$ and the circular flow number $\Phi_c(G)$ in the unsigned case is simple: $\Phi(G) = \lceil \Phi_c(G)\rceil $. Based on this result Raspaud and Zhu conjectured, that $\Phi(G,\sigma) - \Phi_c(G,\sigma) < 1$ for every flow-admissible signed graph $(G,\sigma)$. This conjecture was disproved using noncubic signed graphs with bridges.
In this talk we disprove the conjecture even for bridgeless signed cubic graphs. We also determine all possible pairs of flow and circular flow number of signed cubic graph if flow number is $3, 4$ or $5$ and prove that every pair is achievable. Finally, we prove that every known signed graph with $\Phi(G,\sigma) = 6$ has also $\Phi_c(G,\sigma) = 6$.

♦ ♦ ♦

Snarks are bridgeless cubic graphs which are not 3-edge-colourable. We analyse the structure of all critical cyclically 5-connected snarks up to order 36. The remaining snarks on at most 36 vertices can be constructed from them by using simple operations. Based on this analysis, we generalize certain individual snarks into infinite families and construct a rather rich infinite class of cyclically 5-connected irreducible snarks.

♦ ♦ ♦

Let $G$ be a graph. Its Graovac-Pisanski index is defined as $GP(G)=\frac{|V(G)|}{2|Aut(G)|}\sum_{u\in V(G)}\sum_{\apha\in Aut(G)}d_G(u,\alpha(u))$, where $Aut(G)$ is the group of automorphisms of $G$. It is easy to see that $G$ has the smallest Graovac-Pisanski index if its group of automorphisms is trivial, in which case $GP(G)=0$. The question is to find graphs with the largest value of Graovac-Pisanski index. We found graphs with the maximum value of Graovac-Pisanski index in the class of trees and in the class of unicyclic graphs.

♦ ♦ ♦

The oddness of a cubic graph is the smallest number of odd circuits in a 2-factor of the graph. Oddness constitutes one of the most important measures of uncolourability of cubic graphs. In a previous talk (delivered earlier this year by M. Skoviera) we showed that the smallest number of vertices of a snark with cyclic connectivity 4 and oddness 4 is 44. In this talk we show that there are exactly 31 such snarks. These snarks are built up from subgraphs of the Petersen graph and a small number of additional vertices. Depending of their structure they fall into six classes. We indicate the reasons why these snarks have oddness 4 and sketch the proof that the 31 snarks form a complete set snarks with cyclic connectivity 4 and oddness 4 on 44 vertices.
(This is joint work with Jan Goedgebeur and Martin Škoviera)

♦ ♦ ♦

A graph with chromatic number k is called k-chromatic. Using computational methods, we show that the smallest triangle-free 6-chromatic graphs have at least 32 and at most 40 vertices.
We also determine the complete set of all triangle-free 5-chromatic graphs up to 23 vertices and all triangle-free 5-chromatic graphs on 24 vertices with maximum degree at most 7. This implies that Reed's conjecture holds for triangle-free graphs up to at least 24 vertices. Next to that, we determine that the smallest regular triangle-free 5-chromatic graphs have 24 vertices. Finally, we show that the smallest 5-chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4-chromatic graphs of girth at least 6 have at least 25 vertices.

♦ ♦ ♦

A star edge-coloring of a graph is a proper edge-coloring without bichromatic paths and cycles of length four. In this talk, we present bounds for various classes of graphs. In particular, we focus to the list version of this edge-coloring and prove that the list star chromatic index of every subcubic graph is at most 7, answering the question of Dvořák et al. (Dvořák, Mohar, and Šámal, Star chromatic index, J. Graph Theory 72 (2013), 313-326).

♦ ♦ ♦

If we denote by $n(k, d)$ the order of the largest undirected graph of maximum degree $k$ and diameter $d$, and by $M(k,d)$ the corresponding Moore bound, then $n(k,d) \leq M(k,d)$, for all $ k \geq 3, d \geq 2 $. While the inequality has been proven strict for all but very few pairs $k$ and $d$, the exact relation between the values $n(k,d)$ and $M(k,d)$ is unknown, and the uncertainty of the situation is captured by a question of Bermond and Bollobas who asked whether it is true that for any a positive integer $c>0$ there exist a pair $k$ and $d$, such that $n(k, d)\leq M(k,d)-c$.
We show a surprising connection of this question to the value $2\sqrt{k-1}$, which is also essential in the definition of the Ramanujan graphs which are $k$-regular graphs having the property that their second largest eigenvalue (in modulus) does not exceed $2 \sqrt{k-1}$. We further reinforce this surprising connection by showing an interesting consequence of a negative answer to the problem of Bermond and Bollobas. Namely, we show that if there exists a $c > 0$ such that $ n(k,d) \geq M(k,d) - c $, for all $ k \geq 3, d \geq 2 $, then for any fixed $k$ and all sufficiently large $d$'s, the largest undirected graphs of degree $k$ and diameter $d$ must be Ramanujan graphs. Since Ramanujan graphs are scarce, our result seems to suggest a positive answer to the question of Bermond and Bollobas.
This is a joint work with Slobodan Filipovski.

♦ ♦ ♦

Suppose one is given a finite connected graph X and a group of automorphisms G acting on it. Can one find a regular covering projection onto X such that G is the maximal group that lifts and such that the full automorphism group of the graph is the lift of G? A recent partial answer proved recently by Pablo Spiga and the speaker will be presented.

♦ ♦ ♦

It is known that the class of regular maps can be identified with the class of groups with a presentation G=$. Generally we expect that the group elements 1, a, b, c and bc are pairwise distinct.
In the first part of the talk we give the classification of the maps which fail to meet such expectation, based on the results of C. H. Li and J. Siran.
In the second part of the talk we discuss the construction which gives a self-dual and self-Petrie-dual regular map from any given regular map and study the properties of self-dual and self-Petrie-dual regular maps

♦ ♦ ♦

The concept of a group locally embeddable into finite groups (LEF-group) was introduced by Vershik and Gordon in 1998 to be a group where every finite square cut out of its multiplication table can be extended to a multiplication table of a finite group.
Glebsky and Gordon showed (2005) that a group is locally embeddable into finite semigroups if and only if it is an LEF-group, and that every group is locally embeddable into finite quasigroups, and even into finite loops. Improving on their result Ziman in 2005 proved that every group, as well as every loop having antiautomorphic two-sided inverses is locally embeddable into finite AAI~loops. However, the AAI loops are still "rather far away from groups" in general. A much closer class to groups is formed by the loops satisfying the so called inverse property. We show that every IP-loop, henceforth every group, is locally embeddable into finite IP-loops. The proof makes use of Steiner triple systems and Dirac's theorem for graphs containing a Hamilton cycle.

♦ ♦ ♦

We will discuss ways of establishing the existence of a finite regular self-dual and self-Petrie-dual map of valency k for every positive integer k>3 (a joint work with Olivia Jeans and Jay Fraser).

♦ ♦ ♦

Thomassen's conjecture claims the existence of a constant c such that every cubic graph of cyclic connectivity at least c is hamiltonian. In fact, the only known cyclically 7-connected cubic graph that is not hamiltonian is the Coxeter graph. In 1996, Nedela and Skoviera proved that for cubic vertex-transitive graphs the cyclic connectivity is equal to the girth. By a folklore conjecture, all cubic Cayley graphs are hamiltonian. Suppose that the Thomassen's conjecture holds for c=7. Then to prove hamiltonicity of the cubic Cayley graphs one needs to deal with graphs of girth at most six. The existence of small cycles in a Cayley graph put restrictions on the structure of the underlying group. In our talk we discuss the structure of the cubic Cayley graphs of girth at most six and in many cases show their hamiltonicity. The remaining "hard cases" will be described.

♦ ♦ ♦

The oddness of a bridgeless cubic graph $G$ is the smallest number of odd circuits in a 2-factor of $G$. Oddness is one of the most important invariants of snarks because several important conjectures in graph theory can be reduced to snarks of oddness 4 or larger. In this talk we deal with the problem of determining the smallest order of a nontrivial snark of oddness 4. (Here `nontrivial' means girth at least 5 and cyclic connectivity at least 4.) We prove that the smallest order of a nontrivial snark with oddness 4 and cyclic connectivity 4 is 44, and characterise all snarks of order 44 with this property. The proof relies on a detailed analysis of 3-edge-colourings conflicting on a cycle-separating 4-edge-cut, an extensive computer search, and a closure theorem for cubic graphs with cyclic connectivity 4 due to Andersen, Fleischner, and Jackson (1988).
This is a joint work with Jan Goedgebeur and Edita Mačajová.

♦ ♦ ♦

The past decade has witnessed an increasing role of finite geometry in quantum information theory. In this talk we shall focus on projective ring lines, polar spaces and (extended) generalized polygons. First, we shall show how projective lines over modular rings are related to single-qudit Pauli groups. Then, it will be demonstrated how symplectic and orthogonal polar spaces describe properties of multi-qubit Pauli groups. Finally, it will be outlined how certain black-hole entropy formulas are encoded in the structure of generalized quadrangles with lines of size three and their extensions.

♦ ♦ ♦

The family of Sierpinski graphs has been studied very often in the past few decades for different reasons. One of them is definitely their relation to the famous Sierpinski tringle fractal and their fractal-like structure. Main building block of Sierpinski graphs are complete graphs and each next iteration is built in the fractal-like manner of a complete graph. This idea was recently generalized to generalized Sierpinski graphs, where instead of initially taking a complete graph, we start with an arbitrary graph G. Next iterations are then build in the same manner as graph G is constructed.
We have generalized this idea even further by defining a Sierpinski product of two arbitrary graphs G and H, where we take |G| copies of a graph H and connect these according to edges in graph G. So intuitively we get a graph with local structure of H, but global structure of G. That is if we contract all copies of H, we get a copy of graph G.
In the talk I will describe the Sierpinski product and related constructions, and list some of their basic properties and examples.

♦ ♦ ♦

A signed graph G is said to be determined by its spectrum if every signed graph with the same spectrum as G is switching isomorphic with G. It will be proved that the path P_n, interpreted as a signed graph, is determined by its spectrum if and only if n = 0, 1, or 2 (mod 4), unless n \in {8, 13, 14, 17, 29}, or n = 3.
This is a joint work with Saieed Akbari, Willem H. Haemers, and Hamid Reza Maimani.

♦ ♦ ♦

We prove that every 3-edge-connected graph has a 3-flow that takes on a zero value on at most one sixth of the edges. The graph $K_4$ demonstrates that this $1/6$ ratio is best possible; there is an infinite family where $1/6$ is tight. The proof involves interesting work with connectivity of the graph (relaxing to subdivisions of 2-edge-connected graphs and then reducing to cyclically 4-edge-connected ones).
Joint work with M. DeVos, J. McDonald, I. Pivotto, and E. Rollova.

♦ ♦ ♦

I will cover two main topics. The first one is group connectivity namely proving that Z_4-connectivity does not imply Z_2^2-connectivity, which answers a question suggested by Jaeger et al. [Group connectivity of graphs – A nonhomogeneous analogue of nowhere-zero flow properties, JCTB 1992].
Our proof is computer aided but uses a nontrivial enumerative algorithm.
In the second part I will present our approach to the following conjecture of Matt DeVos: If there is a graph homomorphism from Cayley graph Cay(M, B) to another Cayley graph Cay(M', B') then every graph with (M, B)-flow has (M', B')-flow. This conjecture was originally motivated by the flow-tension duality. We show that a natural strengthening of this conjecture does not hold in all cases but we conjecture that it still holds for an interesting subclass of them and we prove a partial result in this direction. We also show that the original conjecture implies the existence of oriented cycle double cover with a small number of cycles.

♦ ♦ ♦

♦ ♦ ♦

V prednáške nás bude zaujímať výpočtová zložitosť nasledujúceho problému, parametrizovaného dvoma triedami grafov G1, G2: pre daný graf G treba nájsť minimálny počet operácií vymazanie hrany / pridanie hrany tak, aby sme získali graf pozostávajúci z dizjunktného zjednotenia nejakého grafu z G1 a nejakého grafu z G2. Najprv ukážeme, že pre špeciálny prípad, keď G1 je trieda úplných grafov a G2 trieda grafov bez hrán je problém NP-ťažký, aj keď vstupný graf obmedzíme na triedu bipartitných grafov. Naopak, pre triedu planárnych grafov je polynomiálne riešiteľný. Ďalej spomenieme zovšeobecnenia pre editovanie na triedu "hustých" a "riedkych" grafov a budeme skúmať ich parametrizovanú zložitosť.

♦ ♦ ♦

A cycle cover of a graph is a collection of cycles such that each edge of the graph is contained in at least one of the cycles. The length of a cycle cover is the sum of all cycle lengths in the cover. We prove that every bridgeless cubic graph on m edges has a cycle cover of total length less than 1.571m. If the graph has no non-trivial 3-edge-cuts, then a cycle cover of total length less than 1.567m exists.

♦ ♦ ♦

It is known that the monodromy group of any regular unoriented map ${\cal M}$ can be uniquely (up to isomorphism) represented as an abstract group $G$ with a triple $(a,b,c)$ of involutory generators such that $ac=ca$. In this representation operators of duality, Petrie-duality and $e$th-hole operator can be interpreted as the change of the generating triple to the triple $(c,b,a)$, $(ac,b,c)$ and $(a,(bc)^{e-1},c)$, respectively. Regular map ${\cal M}$ which is invariant with respect to all of the above operators (for $e$ co-prime to the valency of ${\cal M}$) is said to be {\em kaleidoscopic regular map with trinity symmetry (KRT)}. We say that a KRT is {\em minimal} if it covers no KRT besides itself and the trivial map. In this talk we recall how the algebraic description of regular maps and their operators can be obtained. Further, we characterize minimal KRTs as least common covers of special families of regular maps with simple monodromy groups. We also presents results of exhaustive computer search with focus on KRTs of odd valency and KRTs with simple monodromy groups.

♦ ♦ ♦

We generalise the well-known fact about the existence of nowhere-zero 2-flows in Eulerian graphs by showing that every signed Eulerian graph which admits an integer nowhere-zero flow has a nowhere-zero 4-flow. We also describe signed Eulerian graphs with flow number 2, 3, and 4, as well as those that do not have an integer nowhere-zero flow. The most difficult part of the proof is to characterise signed Eulerian graphs whose flow number equals 3, which requires proving a decomposition theorem for unsigned 6-regular graphs of odd order. In turn, the proof of latter result calls for the use of signed graphs as a technical tool. Finally, we discuss the existence of nowhere-zero A-flows on signed Eulerian graphs for an arbitrary Abelian group A.
The talk is based on a joint work with Martin Škoviera.

♦ ♦ ♦

♦ ♦ ♦

We report about recent results, related to constructive enumeration (up to isomorphism) of some classes of coherent configurations (CC). Computer aided techniques, used by younger colleagues, goes back to the traditions of Soviet school, and in particular to Igor A.Faradzev. Special attention is payed to so-called non-Schurian objects, those, which are not related to the centralizer algebra of a suitable permutation group.
For a long while the smallest known non-Schurian objects were on 15, 16 and 18 points. Non-Schurian doubly regular tornament on 15 points, due to Dima Pasechnik, will be mentioned.
At the beginning, enumeration of small strongly regular designs (SRDs), in the sense of Donald Higman, will be briefly discussed, basing on the results of MK with Sven Reichard.
The cantral part of the talk will be related to the enumeration of all CCs on up to 15 points (MZA). The main consequence of this enumeration is that all CCs on up to 13 points are Schurian. There exists exactly one new rank 11 non-Schurian CC M with two fibres on 14 points. There are two non_Schurian CCs on 15 points. A friendly computer free interpretation of the new CC M will be given in terms of an SRD with 8 vertices and 6 blocks.
If time will allow, a history of enumeration of Schur rings over groups of order up to 64 will be considered, with special emphasis on results by MZA and Sven Reichard.

♦ ♦ ♦

Let G be a signed complete or complete bipartite graph. We state some properties of the spectrum of the adjacency matrix of G. Also, if the negative edges of G form a matching, we determine the spectrum exactly. Moreover, we give two types of constructions of signed complete graphs whose spectra are symmetric.

♦ ♦ ♦

Magic-type labelings of graphs have been studied for about 50 years. There are literally hundreds of papers in this area. The dynamic survey on graph labelings maintained by Joe Gallian has about 90 pages just on magic-type labelings. The results include general techniques for constructions, mostly based on algebraic properties, special techniques developed for particular classes of graphs as well as necessary conditions based on parity, modularity or graph structure.
In this talk we present two applications of certain magic-type labelings: scheduling tournaments and storing sparse matrices. Moreover, we summarize related results on regular distance magic graphs.

♦ ♦ ♦

We prove that a bridgeless cubic graph $G$ of girth $6$ on $n$ vertices has a $2$-factor $F$ such that at most $9/13 \cdot n$ vertices of $G$ are in circuits of length $6$ of $F$. Dvořák, Kráľ, and Mohar [Z. Dvořák, D. Kráľ, B. Mohar: Graphic TSP in cubic graphs, arXiv:1608.07568] proved that every simple $2$-connected cubic graph on $n$ vertices contains a spanning closed walk of length at most $9/7 \cdot n-1$. We use the technique from our proof to provide an alternative and shorter proof of this statement. Our analysis of $6$-circuits is sufficiently strong, so that limiting aspect for further improvement is the lack of analysis of the $7$-circuits. We provide a very basic analysis of $7$-circuits to show that there exists $\epsilon>0$ such that every simple $2$-connected cubic graph on $n$ vertices contains a spanning closed walk of length at most $(9/7 - \epsilon) \cdot n-1$.

♦ ♦ ♦

The circumference deficit of a graph G is the difference between order and circumference of G. The circumference ratio of a graph G is the ratio of circumference to order of G. We observe that a snark with large resistance has large circumference deficit. By applying several recent results on resistance of snarks, we are able to construct infinite families of cyclically k-connected cubic graphs with circumference ratio less than 1 for each k between 2 and 6. We extend these results to snarks of large girth, solving a problem proposed by Markstrom.
In addition, we construct a non-trivial snark of order 8k and circumference 7k+2 for each integer k above 2. This result contrasts a corollary of the dominating cycle conjecture saying that each non-trivial snark G contains a cycle of length at least 0.75|V(G)|.

♦ ♦ ♦

In the generalized truncation construction, one replaces each vertex of a k-regular graph G with a copy of a graph H of order k. We investigate the symmetry properties of the graphs constructed in this way, especially in connection to the symmetry properties of the graphs G and H used in the construction. We demonstrate the usefulness of our results by using them to obtain a classification of cubic vertex-transitive graphs of girths 3, 4, and 5.
We also address the question of the hamiltonicity of the obtained graphs.
This is joint work with Primoz Sparl from the University of Ljubljana.

♦ ♦ ♦

In this talk we develop the idea that embedding a cubic graph into a closed surface can serve as a convenient tool for finding a Hamilton cycle in it. We establish a necessary and sufficient condition for a cubic graph embedded in a closed surface, orientable or not, to have a bounding Hamilton cycle. With this characterisation and its consequences we can guarantee Hamilton cycles in wide classes of cubic graphs. Among others, we provide a unified and relatively short proof of a result due to Glover, Marusic, Kutnar, and others proved in a series of four papers published over the years 1996-2012 that cubic Cayley graphs of finite quotients of the modular group have a Hamilton path and, except in one special case, they also have a Hamilton cycle. We further show that in the remaining case these graphs have no bounding Hamilton cycle.
This is a joint work with Roman Nedela.

♦ ♦ ♦

Let $G$ be a $d$-regular cyclically $(d-1+2k)$-edge-connected graph (with $k\geq 0$) of even order. A leaf matching operation (LMO) on $G$ consists of removing a vertex of degree $1$ together with its neighbour from $G$. We show that for any given set $X$ of $d-1+k$ edges, there is no $1$-factor of $G$ avoiding $X$ if and only if either an isolated vertex can be obtained by a series of LMO operations in $G-X$ or $G-X$ has an independent set that contains more than half of the vertices of $G$. We show how signed graphs are useful to verify the two conditions of the statement by proving several statements on cubic graphs. We prove that for every integer $k$, if $G$ is sufficiently cyclically edge-connected, then for any three distant paths, there exists a $2$-factor of $G$ that contains one of these paths. For paths of length $3$ and $4$ we analyse the cases when only one or two (possibly intersecting) paths are given. As a consequence, we obtain that for cyclically 7-edge-connected cubic graph $G$ and a vertex $v$ of $G$ there exists a $2$-factor such that $v$ is in cycle of length greater than $7$.
This is joint work with Edita Rollová (University of West Bohemia, Pilsen, Czech Republic).

♦ ♦ ♦

Let G be a bridgeless graph. A circuit cover \CC of G is a collection of circuits such that each edge of G is contained in some circuit from \CC. The length of \CC is the sum of the lengths of the circuits from \CC. The problem of finding short circuit cover can be reduced to weighted cubic graph (where the weights represent lengths of the edges). We show that a bridgeless cubic unweighted graph G has a circuit cover of total length at most 1.6 |E(G)|. Stronger bounds can be obtained if the structure of 5-circuts in G is restricted or when higher cyclic connectivity is assumed.

♦ ♦ ♦

In the context of several algorithmic problems, we shall discuss results about the complexity of the Cayley recognition and the Cayley isomorphism problems. We shall present a new result, done in the collaboration with I. Ponomarenko, that for graphs on 4p vertices these problems can be solved in a polynomial time. In our proof, as is the case also in the recent Babai's result on the complexity of the graph isomorphism problem, the Weisfeiler-Leman stabilisation algorithm producing the smallest coherent algebra for a prescribed set of integer matrices plays an important role.

♦ ♦ ♦

Let $\Gamma$ be a connected graph. A matching $M$ of $\Gamma$ is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex. A vertex of $\Gamma$ is matched by a matching $M$ if it is an endpoint of one of the edges in $M$. A perfect matching of $\Gamma$ is a matching which matches all vertices of $\Gamma$. Graph $\Gamma$ of even order is $n$-extendable, if (i) it contains a matching of size $n$ and (ii) every such matching is contained in a perfect matching of $\Gamma$.
In this talk we will review known results about extendability of strongly regular graphs, distance-regular graphs and Deza graphs.

♦ ♦ ♦

Distance-balanced graphs (that is graphs in which for every pair of adjacent vertices u and v the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u) have been studied to some extent in recent years, investigating different structural properties of such graphs and also the connection of this property to symmetries of graphs. In this talk we present a very natural generalization of the concept of distance-balanced graphs to so-called n-distance-balanced graphs, which was first introduced by Boštjan Frelih in 2014. We discuss some basic properties of n-distance-balanced graphs, give examples of such graphs and present a characterization of such graphs of small diameter. We also discuss the n-distance-balanced property for some well-known families of graphs such as the family of generalized Petersen graphs and pose a number of open problems. This is joint work with Štefko Miklavič.

♦ ♦ ♦

In the first part of the talk we deal with simple labeled graphs with non-zero labels in a ring. If the adjacency matrix of such a graph is invertible, its inverse is an adjacency matrix of another graph, the inverse of the original graph. If the ring is ordered, then balanced inverses - those with a positive product of labels along every cycle - are of interest. We introduce the concept of a derived labeled graph and show how it can be embedded into an inverse. We also prove a new result on balanced inverses of labeled trees and present a construction of new labeled graphs with balanced inverses from old.
In the second part we investigate the so-called positively and negatively invertible graphs. The class of negatively invertible graphs turns out to contain models of important organic molecules and invertibility allows to derive bounds on the binding energy of such molecules. We will present a fairly general construction of new invertible graphs based on `bridging' a pair of invertible graphs, which, informally, means `joining' the pair by a new bipartite graph attached to the two graphs at suitable subsets of vertices.
This is a joint work with Daniel Ševčovič.

♦ ♦ ♦

A geometric graph is a graph drawn in the plane such that its n vertices are points in general position, and its edges are straight-line segments. Two edge-disjoint geometric subgraphs *cross* if there is an edge in the first subgraph and an edge in the second subgraph that have an interior point in common. A set of edge-disjoint geometric subgraphs is called *mutually crossing* if any two of their elements cross. We show that for any geometric complete graph there always exists a set of mutually crossing 2-paths (paths of length 2) of size at least \sqrt{n/2}, and a set of mutually crossing claw graphs (a star of tree leaves) of size at least n/6.
This is a joint work with Dolores Lara (Departamento de Computación, CINVESTAV, Mexico).

♦ ♦ ♦

The Cage Problem is the problem of finding the smallest $k$-regular graphs of girth $g$, called $(k,g)$-cages, for any parameter pair $k,g \geq 3$. Moore bounds are very natural lower bounds on the orders of cages that have been around since the introduction of the Cage Problem in the 1960's. Even though they are generally assumed to be rather poor predictors of the actual orders of cages, no significant improvements on these lower bounds are known to date. In our talk, we present a technique for improving the Moore bounds based on counting cycles of lengths close to the girth $g$ in graphs of orders close to the Moore bounds. The numbers of these cycles together with certain divisibility constraints allow us to exclude specific orders of potential cages for infinite families of parameter pairs $k,g$. We present an overview of the use of this technique in the context of cages as well as some recent results obtained in collaboration with Tatiana Jajcayova and Slobodan Filipovski.

♦ ♦ ♦

A resolving set for a graph is a collection of its vertices such that all vertices are uniquely determined by their distances to the chosen vertices. The metric dimension of a graph G is the smallest size of a resolving set for G. The resolving sets are interesting objects in their own right, but their study is also motivated by the straightforward inequality stating that the metric dimension of a graph gives an upper bound on the base size of its automorphism group.
In the talk we consider resolving sets for the incidence graphs of various symmetric designs, in particular projective, affine and biaffine planes and generalized quadrangles. We give lower estimates on their metric dimensions and construct several different resolving sets. The estimates come from nontrivial double counting arguments and from deep theorems about the sizes of double blocking sets, while the constructions are based on the geometric properties of the designs.
This is a joint work with D. Bartoli, T. Heger and M. Takats.

♦ ♦ ♦

By Frucht's Theorem, every abstract finite group is isomorphic to the automorphism group of some graph. In 1975, Babai characterized which of these abstract groups can be realized as the automorphism groups of planar graphs. In the talk, 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 obtained as semidirect product of a direct product of these stabilizers with a spherical group. As a result we get a characterization similar to the Jordan's characterization of automorphism groups of trees.
Our approach is based on the decomposition to 3-connected components (a modified Trachtenbrot decomposition) and gives a quadratic-time algorithm for computing the automorphism group of a planar graph.
This is a joint work with P. Klavik and P. Zeman.

♦ ♦ ♦

In 1981, Seymour proved that it is possible to assign values 1,2,3,4,5 to edges of an oriented graph in such a way that for every vertex the sum of incoming values equals the sum of outgoing ones. In this talk we will present a new proof of this theorem that uses induction.
This is a joint work with Matt DeVos and Robert Šámal.

♦ ♦ ♦

In this talk we discuss strongly regular graph from combinatorial and algebraic points of view. We review their main properties, related open problems, and their impact on other areas of mathematics. A possible generalization to the directed case will be given at the end of the talk.

♦ ♦ ♦

In this talk we present a construction of Cayley graphs of diameter two with order 200/289 (d+1)^2 for every degree d=17n-1, where n=1 (mod 10) is a prime.
In addition, using explicit estimates for the distribution of primes in arithmetic progressions, we show that for every degree d>=360756 there is a Cayley graph of diameter two and of order at least 0.684 d^2.

♦ ♦ ♦

An L(2,1)-labelling is a labelling of the vertex set of graph with non-negative integers such that the labels of adjacent vertices differ by at least 2 and the labels of vertices at distance 2 are distinct. It is required to determine, for a given graph G, the smallest integer k such that G admits an L(2,1)-labelling with integers not exceeding k; this invariant is denoted by $\lambda(G)$. Determining $\lambda(G)$ is known to be a hard problem. To test whether $\lambda(G) \leq k$ is NP-complete even for series-parallel graphs. On the other hand, there exist classes of graphs where this problem is polynomially solvable (e.g. trees or their mild generalisations). In this talk we derive tight upper and lower bounds for the $\lambda$-number of cacti. We also present a polynomial-time algorithm which computes the $\lambda$-number of an arbitrary cycle-tree (cactus with disjoint cycles).

♦ ♦ ♦

Eye Tracking technology is a rapidly developing area used in manyscientific disciplines. The presentation will be about basic concepts of Eyetracking, interesting practical uses and applications of graph theory in the data evaluation.

♦ ♦ ♦

1. Almost homomorphisms and approximations of groups.
2. Metric approximations of discrete groups. Topological approximations. Equivalent definitions.
3. Sofic groups. Hyperlinear groups. Weakly sofic groups. Linear sofic groups.
4. Equations over groups. Kervaire-Laudenbach conjecture.
5. SQ-universality, congruence extension property, and soficity. The nonstandard extension of a free group.
6. If time permits I will touch the approximations of topological groups.

♦ ♦ ♦

A graph G is called ab-perfect if a(H) equals b(H) for any induced subgraph H of G and any two different parameters "a" and "b" of G. With this definition, perfect graphs are the wX-perfect graphs where "w" is the clique number and "X" is the chromatic number.
In this presentation, we give forbidden graphs characterizations for several classes of ab-perfect graphs when "a" and "b" are parameters related to the clique number, complete colorings - any two colors have an edge in common - and the Hadwiger number - the order of the largest complete minor of a graph. We also show that some classes of graphs such as chordal graphs, cographs and trivially perfect graphs are a type of ab-perfect graphs.

♦ ♦ ♦

In this talk we will present a new algorithm for the efficient generation of all non-isomorphic cubic graphs. We will also show how this algorithm can be extended for the efficient generation of all non-isomorphic snarks. Snarks are of interest since for a lot of interesting open conjectures it can be proven that if the conjecture is false, the smallest possible counterexamples will be snarks.
Our implementation of this algorithm to generate snarks is more than 30 times faster than former generators for snarks. Using this generator we were able to generate all snarks up to 36 vertices. The new list of snarks allowed us to find counterexamples for several published open conjectures.

♦ ♦ ♦

We prove that every 6-edge-connected eulerian graph of order n >= 2 containing a vertex of degree 6 can be transformed into a 6-edge-connected eulerian graph of order n-1 by removing the vertex and reinstating regularity. A similar result also holds when 6 is replaced with 4 or 2. We conjecture that 6 can be replaced by any even positive number.
This is a joit work with Edita Macajova.

♦ ♦ ♦

A Steiner system S(2,k,v) is a design (V,β) where V is a set of v points and β is a collection of k-element subsets of V called blocks such that every 2-element subset of V is contained in exactly one block. In a system (V,β), any set of pairwise disjoint blocks makes a partial parallel class. A partial parallel class that partitions V is a parallel class ; if a partial parallel class partitions V \ {x} for some point x then it is called an almost parallel class.
A proper block coloring of a design (V,β) is a mapping c : β → C such that for any two blocks B,B′ ∈ β, if c(B) = c(B′) then B ∩ B′ = Ø. The minimum number of colors needed to color blocks in (V,β) is called its chromatic index.
Basic results and open problems in proper block colorings of designs will be discussed, mostly in the case of Steiner systems S(2,k,v) for k = 3 (i.e. Steiner triple systems) and for k = 4. In particular, classes of systems for which the chromatic index attains its minimum will be presented.
Special attention will be given to projective triple systems. Let W_m be an (m + 1)-dimensional vector space over F₂ and ⊕ be an operation of vector addition in W_m (performed modulo 2 componentwise). A projective triple system (V,β) is a Steiner triple system in which each point in V is represented by a non-zero vector in W_m and every two distinct points, corresponding to vectors x and y, define a unique triple formed by {x,y,x⊕y}. The exact value for the chromatic index of projective triple systems will be determined, together with a polynomial time algorithm to obtain such a coloring.
In relation to proper block coloring, main results on the existence of parallel classes and almost parallel classes in Steiner systems S(2,k,v) will be discussed.

♦ ♦ ♦

A family F of automorphisms of a vertex-transitive graph G is said to be k-regular if for every pair u,v of vertices of G there exist k automorphisms in F mapping u to v. Every vertex-transitive graph admits a k-regular family for some positive k, and quasi-Cayley graphs are vertex-transitive graphs admitting a 1-regular family of automorphisms. We investigate the class of merged Johnson graphs with regard to the parameter k, classify merged Johnson graphs that are Cayley, and relate this topic to that of the existence of a uniform routing.

♦ ♦ ♦

A map is a cellular embedding of a graph into a compact surface. Regular maps are those with highest possible level of symmetry - whose automorphism groups act regularly on their flag sets. In this talk we will present an enumeration of orientably-regular maps with automorphism group isomorphic to the group $M(q^2)$ - so called twisted linear fractional group. We will also mention some open questions about external symmetries (e.g. self-duality) of these regular maps.
(This is a joint work with G. Erskine and J. Širáň.)

♦ ♦ ♦