Abstrakt:

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.

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

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á.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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)

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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^{2})

(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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

A sequence r_{1}, r_{2},...,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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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áň.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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].

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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$.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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$.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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)

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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á.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Decompositions of complete bipartite graphs into prisms revisited

or

Odvolávavám, co jsem odvolal, a slibuji, co jsem slíbil

♦ ♦ ♦

Abstrakt:

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ť.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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$.

♦ ♦ ♦

Abstrakt:

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)|.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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č.

♦ ♦ ♦

Abstrakt:

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č.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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).

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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_{2} 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.

♦ ♦ ♦

Abstrakt:

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.

♦ ♦ ♦

Abstrakt:

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áň.)

♦ ♦ ♦

Abstrakt:

A few years ago, Gabriel Verret, Pablo Spiga, and myself compiled a complete list of all connected vertex-transitive graphs of valence 3 on not more than 1280 vertices. In my talk, I will try to explain how this was done.

♦ ♦ ♦

Abstrakt:

A permutation snark is a cubic graph with no 3-edge-colouring that contains a 2-factor consisting of two induced circuits. In the talk we analyse the basic properties of permutation snarks, focusing on the structure of edge-cuts of size 4 and 5. As an application of our knowledge we provide rich families of cyclically 4-edge-connected and 5-edge-connected permutation snarks of order 8n+2 for each integer n >= 2 and n >= 4, respectively, superseding a recent work of J. Hagglund and A. Hoffmann-Ostenhof.

This talk reports an ongoing research with Edita Macajova.

♦ ♦ ♦

Abstrakt:

V prednáške zavedieme dôležitý algebraický invariant grafu - Jakobián. Pre daný graf G jeho Jakobián Jac(G) je istá konečná abelovská grupa definovaná grafom G. Ukážeme, ako Jakobián grafu súvisí s celočíselnými tokmi na grafoch a ako ho vypočítať. Je známe, že počet kostier súvislého grafu je rovný počtu prvkov Jakobiánu. Teda na kostrách grafu môžeme definovať operáciu sčitovania, avšak nie je jasné, ako to urobiť prirodzeným spôsobom. Kombinatorický význam ďalších invariantov Jakobiánu nie je známy (napríklad rank, alebo maximálny rád prvku). Jakobián grafu sa pekne správa vzhľadom na isté špeciálne typy grafových epimorfizmov, ktoré nazývame harmonické morfizmy. Otvorená je aj otázka odvodenia Jakobiánu v tvare rozkladu na cyklické grupy pre niektoré jednoduché triedy grafov.

♦ ♦ ♦

Abstrakt:

A Siamese color graph on $40$ is an edge decomposition of $K_{40}$ into the spread (i.e., $10$ vertex disjoint cliques of order $4$) $S$ and four $6$-valent distance regular graphs (DRGs) such that each DRG together with the spread form a strongly regular graph with parameters $(40,12,2,4)$.

We present a motivanion for the study of Siamese color graphs stemming from generalized quadrangles and Steiner system and provide the full classification of objects on $40$ points.

Talk is based on a joint project with M. Klin, S. Reichard and A. Woldar.

♦ ♦ ♦

Abstrakt:

Circulants are important class of vertex-transitive graphs. They have a vast number of applications, for example in telecommunication networking, they are used as models for interconnection networks etc. We discuss the problem of when does the complete graph admit a decomposition into subgraphs each of which is isomorphic to a fixed given circulant.

♦ ♦ ♦

Abstrakt:

The degree diameter problem is concerned with finding the largest order graph subject to constraints on degree and diameter. This problem celebrated its 50th birthday last year and the paucity of results indicates that it will be around for much longer. Apart from the trivial cases (degree = 1 or 2, and diameter = 1) only 7 graphs are known to be largest possible. A sub-problem is to look at the degree diameter problem as subgraphs of some host architecture.

We present here some results and open problems on the degree diameter subgraph problem as applied to the multi-dimensional rectangular mesh, multi-dimensional honeycomb mesh and the triangular grid. The problem is also well suited to families of directed, oriented and mixed graphs. We will present bounds on the oriented rectangular and oriented triangular grids.

Recent work in the field can be accessed in [1, 2, 3, 4].

References:

- A. Dekker, H. Perez-Roses, G. Pineda-Villavicencio, and P. Watters: "The maximum degree & diameter-bounded subgraph and its applications", Journal of Mathematical Modelling and Algorithms 11 no. 3, pp.249268, 2012
- Holub, P., Miller, M., Perez-Roses, H., Ryan, J.: "Degree Diameter Problem on Honeycomb Networks", Discrete Applied Mathematics, Vol 179 31 pp.139-151, 2014
- Holub, P., Ryan, J.: "Degree Diameter Problem on Triangular Networks", Australasian Journal of Combinatorics, in print
- Miller, M., Perez-Roses, H., Ryan, J.: "The maximum degree & diameter-bounded subgraph in the mesh", Discrete Applied Mathematics, Vol.160, pp.1782-1790, 2012

♦ ♦ ♦

Abstrakt:

A semi-transitive orientation of a graph $\Gamma$ is a digraph $\Delta$, disjoint from its reverse, such that $Aut(\Delta)$ is transitive on the vertices and on the edges of $\Gamma$. If $Aut(\Gamma) = Aut(\Delta)$ then we say that $\Gamma$ is 1/2-transitive ( or 1/2-arc-transitive). These are graphs of interest to a lot of us. But in this talk, I would like to explore the opposite direction: Given a graph whose group is known to be transitive on darts (directed edges), when does it have a semi-transitive orientation? How many might it have? Can it have non-isomorphic orientations? etc.

♦ ♦ ♦

Abstrakt:

Navrhovanie experimentov slúži na optimalizáciu množstva informácie získanej z experimentu, pri daných vstupných podmienkach a ohraničeniach. Potreba optimalizácie množstva získanej informácie vznikla kvôli finančnej a časovej náročnosti niektorých experimentov. My sa zameriame na blokové návrhy experimentov, ktoré vieme reprezentovať pomocou párovacích grafov. Vďaka tomu vieme niektoré úlohy z teórie navrhovania experimentov previesť na úlohy z teórie grafov a naopak. Na ilustráciu využitia tohto prepojenia predstavíme výsledky pánov Constantineho a Kelmansa. Týkajú sa grafov s max. počtom kostier a sú založené na práci s vlastnými číslami Laplaciánov. Využitím a rozšírením postupov týchto pánov sme odvodili nové triedy optimálnych návrhov experimentu. Na záver ukážeme namerané výsledky z algoritmu na hľadanie optimálnych návrhov, vďaka ktorým sme vyvrátili jednu hypotézu o silno regulárnych grafoch.

♦ ♦ ♦

Abstrakt:

The enumeration and classification of many regular objects, such as maps, hypermaps, polytopes and covering spaces, with a given automorphism group G, can be reduced to the problem of counting epimorphisms from a certain finitely generated group \Gamma onto G. Philip Hall's theory of Moebius inversion in groups, an algebraic analogue of the inclusion-exclusion principle, reduces this further to the simpler problem of counting homomorphisms from \Gamma to G, and this can often be solved directly or by using character theory. I shall describe the general theory, followed by recent progress, and applications to maps on surfaces, where G belongs to certain families of finite simple groups, such as the Suzuki groups.

(Joint work with Martin Downs.)

♦ ♦ ♦

Abstrakt:

Haar graphs are regular covering graphs of dipoles. They can also be constructed in a Cayley graph-like manner, in terms of a group G and its subset S. Just like Cayley graphs, these graphs frequently appear in various constructions, due to their desirable symmetry properties. For example, Haar graphs were used for constructing families of semi-symmetric graphs and cages.

If G is an abelian group, then its Haar graphs are well-known to be Cayley graphs; however, there are examples of non-abelian groups G and subsets S when this is not the case. Thus it might be worth investigating the Cayley-ness and more generally the vertex-transitivity of Haar graphs.

In this talk we address the problem of classifying finite non-abelian groups G with the property that every Haar graph of G is a Cayley graph. We will deduce an equivalent condition for a Haar graph of G be a Cayley graph of a group containing G in terms of G, S, and Aut(G). Moreover, the above problem will be solved for dihedral groups.

♦ ♦ ♦

Abstrakt:

A graph is called Frobenius if it is a connected orbital regular graph of a Frobenius group. A Frobenius map is a regular Cayley map whose underlying graph is a Frobenius graph. In this talk we show that almost all low-rank Frobenius graphs admit regular embeddings and enumerate non-isomorphic Frobenius maps for a given Frobenius graph. As a result, we produce some Frobenius maps with trivial exponent groups.

This is a joint work with Jin Ho Kwak.

♦ ♦ ♦

Abstrakt:

The largest order of a graph of maximum degree $d$ and diameter $k$ cannot exceed the Moore bound, which has the form $M(d,k)=d^k - O(d^{k-1})$ for $d$ going to infinity and any fixed $k$.

Known results in finite geometries on generalised polygons imply, for $k=2,3,5$, the existence of an infinite sequence of values of $d$ such that $n(d,k)=d^k - o(d^k)$. This shows that for $k=2,3,5$ the Moore bound can be approached asymptotically; moreover, no such result is known for any other value of $k>1$. The corresponding graphs are, however, far from vertex-transitive, and there appears to be no obvious way to extend them to vertex-transitive graphs giving the same type of asymptotic result. We show that for diameters $2$ and $3$ the Moore bound can be approached asymptotically by Cayley graphs using generalized polygons.

This is a joint work with Jozef Siran and Jana Siagiova.

♦ ♦ ♦

Abstrakt:

The well-known Four Color Theorem can be translated to the following statement: "Every plane triangulation G has two spanning (bipartite) quadrangulations such that each edge in G belongs to at least one of them." For triangulations of non-spherical surfaces, although 4 colors do not suffice, we would like to find some properties that are "close" to the 4-colorability. Then, in this talk, as an analogy to the Four Color Theorem in the sense of the above, we will consider whether a triangulation of a surface has a spanning bipartite quadrangulation. Note that this is the dual form of the problem of finding a perfect matching M in a cubic graph on a surface such that M satisfies a certain topological property (namely Z_2-homology). We will explain the above problem for the case of even triangulations of the projective plane and the torus, and introduce several problems.

This is a joint work with Atsuhiro Nakamoto (Yokohama National University) and Kenta Noguchi (Keio University).

♦ ♦ ♦

Abstrakt:

We study the effect of removing a pair of adjacent vertices on the cyclic connectivity of a cubic graph. In general, removing a pair of adjacent vertices cannot decrease cyclic connectivity by more than two. Our main result states that - apart from three exceptional graphs that include the Petersen graph - every bridgeless cubic graph contains a pair of adjacent vertices whose removal decreases cyclic connectivity by at most one. Our research is motivated by the study of the existence of long cycles in embedded cubic graphs and its relationship to maximum genus of a graph.

This is a joint work with M. Kotrbcik and R. Nedela.

♦ ♦ ♦

Abstrakt:

A $k$-regular graph of order $n$ is said to be strongly regular with parameters $(n,k,\lambda,\mu)$ if each pair of adjacent vertices has exactly $\lambda$ common neighbors and each pair of non-adjacent vertices has exactly $\mu$ common neighbors. There exist several necessary conditions for parameter sets to admit the existence of a strongly regular graph. Parameter sets satisfying all of them are called feasible. Although the existence of a strongly regular graph is solved for all feasible parameter sets with $n\leq 50$, the complete classification is still open for parameter sets $(37,18,8,9)$, $(41,20,9,10)$, $(45,22,10,11)$, $(49,24,11,12)$, $(49, 18, 7,6)$ and $(50,21,8,9)$.

By exhaustive computer search we obtain a full list of strongly regular graphs on up to $50$ vertices with an automorphism of order $3$. Further, for parameter sets $(37,18,8,9)$, $(41,20,9,10)$, $(45,22,10,11)$, $(49,24,11,12)$, $(49, 18, 7,6)$ and $(50,21,8,9)$ we determine a class of strongly regular graphs which contains all the $Z_3$ graphs and is closed under particular instances of partial switching defined by Godsil-McKay and Behbahani-Lam-Ostergaard, respectively. As a corollary, we significantly extend list of known regular two-graphs on at most $50$ vertices. (Joint work with A. Koval.)

♦ ♦ ♦

Abstrakt:

During the past decade, many papers devoted to discrete versions of the theory of Riemann surfaces have appeared. The role of Riemann surfaces and holomorphic mappings in these theories is played by finite graphs and harmonic mappings. For these theories, various versions of the Riemann-Hurwitz for mula have been obtained and analogues of the Riemann-Roch theorem have been proved. Many other theorems of the classical theory of Riemann surfaces have also been carried over to the discrete case. In particular, the upper and lower bounds for the order of a group acting harmonically (i.e., without fixed semiedges) on a graph of given genus were found. This result can be regarded as a discrete analogue of well known theorems of Hurwitz (1893) and Accola-Maclachlan (1968), which give sharp upper and lower bounds for the order of an automorphism group acting on a Riemann surface.

The purpose of this report is to provide discrete versions of theorems of Wiman (1895), Oikawa (1956), and Arakawa (200), which sharpen Hurwitz' upper bound for various classes of groups acting on a Riemann surface of given genus.

♦ ♦ ♦

Abstrakt:

A two-graph is a set of (unordered) triples chosen from a finite vertex set X, such that every (unordered) quadruple from X contains an even number of triples of the two-graph. A regular two-graph has the property that every pair of vertices lies in the same number of triples of the two-graph.

In the talk we present connections between two-graphs and various other combinatorial objects, for example Eulerian graphs, conference matrices, and systems of equiangular lines.

♦ ♦ ♦

Abstrakt:

In 1982, Zaslavsky introduced the concept of a proper vertex colouring of a signed graph G as a mapping f:V(G) >Z such that for each edge uv the colour f(u) is different from the colour s(uv)f(v), where is s(uv) is the sign of the edge uv. The substantial part of Zaslavsky's research concentrated on polynomial invariants related to signed graph colourings rather than on the behaviour of colourings of individual signed graphs. We continue the study of signed graph colourings by proposing the concept of a chromatic number for signed graphs as a natural extension of the chromatic number of an unsigned graph. We establish the basic properties of this invariant, provide bounds in terms of the chromatic number of the underlying unsigned graph, investigate the chromatic number of signed planar graphs, and prove an analogue of the celebrated Brooks theorem.

This is a joint work with Edita Macajova and Andre Raspaud.

♦ ♦ ♦

♦ ♦ ♦

Abstrakt:

An $r$-regular family $\F$ of permutations on a set $V$ contains for each pair of vertices $u,v \in V$ exactly $r$ permutations $f \in \F$ mapping $u$ to $v$, $f(u)=v$. Previously, $1$-regular families of graph automorphisms were used by Gauyacq to characterize the quasi-Cayley graphs; a class of vertex-transitive graphs that properly contains the class of Cayley graphs, shares many characteristics of the Cayley graphs, and is properly contained in the class of vertex-transitive graphs.

We introduce the concept of $r$-regular families to cover all vertex-transitive graphs, and to serve as a measurement of how far a vertex-transitive graph is from being Cayley. As any automorphism group of a graph $ \Gamma=(V,E)$ acting transitively on $V$ with a vertex-stabilizer of order $r$ can be easily seen to form an $r$-regular family on $V$, every vertex-transitive graph admits an $r$-regular family of automorphisms for some $r \geq 1$.

♦ ♦ ♦

Abstrakt:

The talk focuses on the circumference of cubic graphs with given cyclic edge-connectivity. 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 its circumference to the order.We observe that a snark with large resistance has a large circumference deficit. Together with our recent results on resistance, this gives a construction of infinite families of cyclically $k$-edge-connected cubic graphs with circumference ratio less than $1$ for each $k\in\{2,3,4,5,6\}$. We extend these results for snarks of large girth, solving a problem proposed by Markstrom et al. In addition, we construct a family of non-trivial snarks of order $8k$ and circumference $7k+2$ for each integer $k\ge 3$. This result contrasts a corollary of the well-known dominating cycle conjecture saying that each non-trivial snark $G$ contains a cycle of length at least $3/4\cdot |V(G)|$.

This is a joint work with Edita Máčajová.

♦ ♦ ♦

Abstrakt:

A cycle cover of a graph G is a collection of cycles in G such that every edge from E(G) is contained in at least one of the cycles. A long open conjecture of Alon and Tarsi states that every bridgeless graph on m edges has a cycle cover of length at most 1.4m. The best known general result for bridgeless graphs is a cycle cover of total length at most 5m/3 [Alon and Tarsi 1985; Bermond, Jackson, and Jaeger 1983]. The nowhere zero 5-flow conjecture implies existence of a cycle cover of length at most 1.6m [Jamshy, Raspaud, and Tarsi 1987]. The best result for bridgeless cubic graphs up to date is by Kaiser et al. (2010) giving a cycle cover of length at most 34m/21 ~ 1.619m. We show that a bridgeless cubic graph G with m edges has a cycle cover of length at most 1.6m. If G contains no circuits of length 5, then it has a cycle cover of length at most 14/9m ~ 1.556m.

This is a joint work with B. Candrakova.

♦ ♦ ♦

Abstrakt:

The traveling salesman problem (TSP) is to find a Hamilton cycle of minimum cost in a complete weighted graph. We consider a special case of TSP, a graphic TSP, where the weights of edges in the complete graph correspond to the lengths of the shortest paths between vertices of some graph $G$. Hence we are looking for the shortest trail in $G$ that contains all vertices of $G$. We call such trail a traveling salesman tour. We further restrict ourselves to bridgeless cubic graphs. We show that if $G$ is a simple connected bridgeless cubic graph on $n \ge 8$ vertices, then $G$ has a traveling salesman tour of length at most $1.3n - 2$. This tour can be constructed in polynomial time.

♦ ♦ ♦

Abstrakt:

A graph G is called (r, s)-edge-choosable if for every assignment of sets of size r to the edges of G it is possible to choose for every edge an s-element subset from its set such that the subsets chosen for any pair of adjacent edges are disjoint. The list fractional chromatic index of a graph G is the infimum of all numbers r/s for which G is (r, s)-edge-choosable. Mohar http://www.fmf.uni-lj.si/~mohar--> (June 2003) posed a problem asking whether every cubic graph is (7,2)-edge-choosable. In 2009, Cranston and West [SIAM J. Discrete Meth., 23 (2009), pp. 872–881] showed that every 3-edge-colorable cubic graph is (7,2)-edge-choosable and gave a sufficient condition with the help of which they proved that many non-3-edge-colorable cubic graphs are (7,2)-edge-choosable. In this paper we prove that every bridgeless cubic graph is (7,2)-edge-choosable. We show that this result cannot be improved in the family of all cubic graphs, in the sense that there exists a cubic graph with list fractional chromatic index 7/2. The original question of Mohar remains open, and we further pose several related problems.

♦ ♦ ♦

Abstrakt:

An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ An incidence of an undirected graph G is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge of $G$ incident with $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent if one of the following holds: (i) $v=w$, (ii) $e=f$ or (iii) $vw=e$ or $f$. An incidence coloring of $G$ assigns a color to each incidence of $G$ in such a way that adjacent incidences get distinct colors. In this talk we present bounds for incidence chromatic number of graphs having high maximum average degree. In particular we prove that every graph with maximum degree at least $7$ and with maximum average degree strictly less than $4$ admits a $(\Delta+3)$-incidence coloring. This result implies that every triangle free planar graph with maximum degree at least $7$ is $(\Delta+3)$-incidence colorable.

♦ ♦ ♦

Abstrakt:

We study the equation $W(L^i(T))=W(T)$, where $T$ is a tree, $L^i$ is the $i$-iterated line graph operator and $W$ stands for the Wiener index, that is, the sum of all distances in a graph.

Melnikov and Dobrynin conjectured that the equation has no solution for $i\ge 3$. We prove their conjecture for $i\ge 4$, while for $i=3$ we find a class of trees $T$ satisfying $W(L^3(T))=W(T)$. Moreover, we prove that trees not belonging to this strictly determined class do not satisfy the equality.

The work is based on 7 joint papers with Riste Skrekovski, Primoz Potocnik and Martin Macaj.

♦ ♦ ♦

Abstrakt:

A graph G is equimatchable if any matching of G is a subset of a maximum-size matching. It is well known that any 2-connected equimatchable graph is either bipartite, or factor critical, and that these two classes are disjoint.

The structure of factor-critical equimatchable graphs with a cut-vertex and 2-cut was investigated in [J. Graph Theory, 10(4):439-448, 1986.]. We extend these results and for all $k\ge 3$ we describe the structure of factor-critical equimatchable graphs with a k-vertex-cut. For every $k\ge 3$, we prove that if a k-connected equimatchable factor-critical graph G has at least 2k+3 vertices and a k-cut S such that G-S has two components with sizes at least 3, then G-S has exactly two components and both are complete graphs. Consequently, such graphs have independence number 2 and differ from an union of two complete graphs by at most k^2/3 edges. Additionally, we provide also a characterisation of k-connected equimatchable factor-critical graphs with a k-cut S such that G-S has a component with size at least k and a component with size 1 or 2. Finally, we show that if every minimum cut S separates a component with size at most two, then the independence number can be arbitrarily high and the number of components can be as high as |V(S)|.

♦ ♦ ♦

Abstrakt:

A truncated triangulation is a 3-valent map on a closed surface S arising from a triangulation of S by truncating each vertex, that is, by expanding it into a contractible cycle. Several years ago, Glover and Marusic implicitly employed truncation of highly symmetrical triangulations of orientable surfaces as a tool for proving the existence of Hamilton cycles in large classes of cubic Cayley graphs. We generalise their method by replacing high symmetry with a somewhat surprising weaker condition - upper embeddability of the dual cubic graph. Our result enables us to construct Hamilton cycles in much wider classes of cubic graphs. For example, we show that the truncation of a triangulation of any closed surface with no separating 3-cycle has a Hamilton cycle whenever the number of faces is 2 (mod 4) and has a cycle missing only two adjacent vertices whenever the number of faces is 0 (mod 4).

This is a joint work with Michal Kotrbcik and Roman Nedela.

♦ ♦ ♦

Abstrakt:

Známy výsledok Plesníka hovorí, že v (d-1)-hranovo-súvislom d-regulárnom grafe existuje perfektné párenie, ktoré neobsahuje žiadnu z d-1 dopredu zvolených hrán. V prednáške sa budeme zaoberať otázkou, či a za akých podmienok je možné zakázať viac hrán za predpokladu vyššej cyklickej hranovej súvislosti. Dokážeme, že v d-regulárnom cyklicky k-hranovo-súvislom grafe (k>=d-1) môžeme nájsť perfektné párenie neobsahujúce dopredu zvolenú množinu X nanajvýš (d+k-1)/2 hrán okrem dvoch situácií:

- Po odstránení množiny X vieme pomocou niekoľkých operácií spárovania vrchola stupňa 1 dostať izolovaný vrchol (t.j. odstránením množiny X sme vytvorili malú konfiguráciu vylučujúcu perfektné párenie, napr. izolovaný vrchol).
- Bez množiny X graf obsahuje nezávislú množinu obsahujúcu viac ako polovicu vrcholov (t.j. graf je takmer bipartitný).

♦ ♦ ♦

Abstrakt:

We show that every bridgeless cubic graph G on n vertices other than the Petersen graph has a 2-factor with at most 2(n-2)/15 circuits of length 5. An infinite family of graphs attains this bound. We also show that G has a 2-factor with at most n/5.83 odd circuits. This improves the previously known bound of n/5.41 [Lukotka, Macajova, Mazak, and Skoviera: Small snarks with large oddness, arXiv:1212.3641

♦ ♦ ♦

Abstrakt:

Moorovský graf s priemerom dva je silno regulárny graf s parametrami (n,k,0,1). Takýto graf má k^2+1 vrcholov a je to aj najväčší možný k-regulárny graf s priemerom 2 a súčasne najmenší možný k-regulárny graf s obvodom 5. Budeme demonštrovať výsledky a techniky spektrálnej teórie grafov na probléme existencie moorovských grafov priemeru dva z článku

*A.J. Hoffman and R.R. Singleton. On moore graphs with diameter 2 and 3.* IBM J. Res. Develop., 4:497 504, 1960.

Podobne na základe článkov

*P. Erdös, S. Fajtlowicz, and A. J. Hoffman. Maximum degree in graphs of diameter 2.* Networks, 10(1):87 90, 1980

*W.G. Brown. On the non-existence of a type of regular graphs of girth 5.* Canadian Journal of Mathematics, 19:644 648, 1967.

preskúmame existenciu k-regulárnych grafov s priemerom 2 s k^2 vrcholmi a k-regulárnych grafov s obvodom 5 s k^2 + 2 vrcholmi.

♦ ♦ ♦

Abstrakt:

Blokový graf steinerovského systému trojíc S=(V,B) je graf, ktorého vrcholmi sú práve bloky systému S a v ktorom sú dva bloky spojené hranou práve vtedy, keď majú spoločný bod. Na vlastnostiach takýchto blokových grafov ilustrujeme metódy a výsledky z článku * R. C. Bose: Strongly Regular Graphs, Partial Geometries, and Partially Balanced Designs, Pac. J. Math. 13 (1963), 389-419*

týkajúce sa geometrických a pseudogeometrických silne regulárnych grafov.

Prednáška neobsahuje algebru.

♦ ♦ ♦

Abstrakt:

Maps are cellular embeddings of graphs on compact surfaces. Regular maps are maps with highest possible level of symmetry. A map is regular if its automorphism group acts regularly on the set of its flags. Enumeration and classification of regular maps is usually approached in three different ways - by supporting surfaces, by underlying graphs, and by automorphism groups.

In this talk we focus on regular maps whose automorphism group is isomorphic to ${\rm PSL}(2,q)$ and ${\rm PGL}(2,q)$ and will characterize those maps which are self-dual, self-Petrie-dual, or Möbius.

♦ ♦ ♦

Abstrakt:

The problem of coloring squares of graphs (or square coloring graphs) has been extensively studied since a 1977 conjecture by Wegner, still widely open. The square of a graph is the same graph with additional edges between every pair of vertices that share a neighbor.

After introducing the topic, we focus on three questions on which progress was recently made:

- Does list coloring make a difference? (Kostochka, Woodall '01) We overview examples of squares of graphs on which list coloring makes a difference, which were discovered this year by Kim and Park, and later generalized by two different groups of people.
- How sparse does a graph have to be, for its square to be colorable with very few colors? (Wang, Lih '03) We survey results on planar graphs with large girth by Borodin et al. over the last few years, and present joint work with Benjamin Lévêque and Alexandre Pinlou which generalizes them to graphs with no assumption on planarity.
- Do many squares of graphs require a lot of colors? (Cranston, Kim'08) We discuss the question, which was answered negatively by Cranston and Rabern this month, and mention joint work with Nicolas Bousquet which generalizes the result to any powers of graphs.

♦ ♦ ♦

Abstrakt:

The notion of a directed strongly regular graph was introduced by Duval as a possible generalization of classical strongly regular graphs. A directed strongly regular graph (DSRG) with parameters $(n,k,\mu,\lambda,t)$ is a regular directed graph on $n$ vertices with degree $k$ such that every vertex is incident with $t$ undirected edges, and the number of paths of length 2 directed from a vertex $x$ to a vertex $y$ is $\lambda$ if there is an arc from $x$ to $y$, and $\mu$ otherwise.

It had been proven by J\o rgensen that a DSRG cannot be a Cayley digraph over an Abelian group. However, there are known several infinite families of DSRGs as Cayley digraphs over semidirect product groups. In this talk we will introduce the first two infinite families over wreath product groups.

♦ ♦ ♦

Abstrakt:

The following two results of Tutte will be the starting point of the talk.

- A cubic graph $G$ is bipartite if and only it has a nowhere-zero 3-flow.
- A cubic graph is 3-edge-colorable if and only if it has a nowhere-zero 4-flow.

♦ ♦ ♦

Abstrakt:

The talk will present a result of K. Kawarabayashi and K. Ozeki. They give a new proof of the disjoint odd cycle theorem which characterizes graphs without two vertex-disjoint odd cycles. The advantage of this proof is its length and simplicity. Unlike the original one from 1990, it does not depend on any result for matroids. The authors use only the well known two path theorem.

♦ ♦ ♦

Abstrakt:

Cages are extremal graphs with respect to given degree and diameter. During the last ten years, we have seen a revival of interest in this topic partially due to the introduction of algebraic and topological methods into the area. In our presentation, we will present a review of these recent developments, mention some of the harder and more fundamental problems that should be addressed next, and generally discuss the direction for further research of the Cage Problem. The talk is meant to attract both colleagues and graduate students into the area.

♦ ♦ ♦

Abstrakt:

Entropy compression je metóda založená na fakte, ze náhodnú postupnosť n bitov nemožno injektívne zobraziť tak, aby mal výsledok menej ako n bitov. V posledných niekoľkých rokoch bola táto metóda použitá pri dôkazoch viacerých zaujimavých výsledkov.

Použitie metódy ukážeme na dvoch tvrdeniach.

- Ukážeme, že logická formula v konjunktívnej normálnej forme, ktorej klauzy majú dĺžku nanajvýš $k$ a pretínajú sa nanajvýš s 2^(k-C) inými klauzami (kde C je vhodná konštanta), je splniteľná.
- Každý graf s maximálnym stupňom \Delta možno zafarbiť 4(\Delta-1) farbami tak, že neexistuje cyklus používajúci iba dve farby.

♦ ♦ ♦

Abstrakt:

Klasické výsledky Williama Tutta o tokoch na kubických grafoch z 50-tych rokov minulého storočia charakterizujú kubické grafy, ktoré pripúšťajú nikde-nulový 3-tok alebo 4-tok. Podobné výsledky pre signované grafy, čo je prekvapujúce, neboli doteraz známe. V prednáške odvodíme charakterizácie kubických signovaných grafov, ktoré pripúšťajú nikde-nulový 3-tok alebo 4-tok alebo toky v abelovských grupách rádu 3 a 4. Väčšina našich charakterizácií využíva signatúru ekvivalentnú s konštantne negatívnou signatúrou známou ako "antibalansovaná". Poukážeme aj na nezvyčajné správanie tokov na signovaných grafoch s hodnotami v konečných abelovských grupách a vyslovíme niekoľko problémov pre ďalší výskum.

Prednáška je založená na spoločnej práci Edity Máčajovej a prednášajúceho.

♦ ♦ ♦

Abstrakt:

We define projective planes and present several results on colorations and graph theory related with them. In particular, we give an overview of the following topics:

- The upper chromatic number and specifically the balanced upper chromatic number in projective planes.
- The notion of the achromatic and pseudoachromatic numbers for the linear graph of the complete graph and their relation to projective planes and,
- A brief description of cages of girth six and their relation with projective planes.

♦ ♦ ♦

Abstrakt:

Autor vo svojej prednáške predstaví niektoré známe aj menej známe súvislosti týkajúce sa vlastností kubických grafov uvedených v názve.

♦ ♦ ♦

Abstrakt:

This talk is concerned with automorphism breaking of finite and infinite graphs. In 1996, Albertson and Collins introduced the distinguishing number D(G) of a graph G as the least cardinal d such that G has a labeling with d labels that is only preserved by the trivial automorphism. This concept has spawned numerous papers on finite and infinite graphs. Here we focus on the infinite motion conjecture of Tom Tucker and generalizations. In particular, we present results pertaining to the conjecture, a generalization to uncountable graphs, and results that support the conjecture and its generalizations.

♦ ♦ ♦

Abstrakt:

The number of vertices of a graph of diameter two and maximum degree $d$ is at most $d^2+1$. This number is the Moore bound for diameter two. The order of largest Cayley graphs of diameter two and degree $d$ is denoted by $C(d,2)$. The only known construction of Cayley graphs of diameter 2 valid for all degrees $d$ gives $C(d,2)>\frac14 d^2+d$. However, there is a construction yielding Cayley graphs of diameter 2, degree $d$ and order $d^2-O(d^{\frac32})$ for an infinite set of degrees $d$ of a special type. In our talk we present a construction giving $C(d,2)\geq\frac12 d^2-k$ for $d$ even and of order $C(d,2)\frac12(d^2+d)-k$ for $d$ odd, $0\leq k\leq 8$. In addition, we show that, in asymptotic sense, the most of record Cayley graphs of diameter two are obtained by our construction.

♦ ♦ ♦

Abstrakt:

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 Jajcayová.

♦ ♦ ♦

Abstrakt:

A $(k;D)$-graph is a (finite, simple) $k$-regular graph of diameter $D$. The Degree/Diameter Problem is the problem of determining the order $n(k;D)$ of the largest $(k;D)$-graphs. The well-known Moore bound serves as an upper bound on the order of $(k;D)$-graphs. In terms of $k$ and $D$, it can be stated as follows:

$M(k; g) = 1 + k + k(k - 1) + \dots + k(k-1)^{D-1}.$

In our talk we show that for any fixed degree $k\geq 3$ and any positive integer $K$ the largest vertex-transitive $(k;D)$ graph has size at most $M(k;D)-K$ for almost all (in the asymptotic sense) diameters $D$.

This is a joint work with G. Exoo, R. Jajcay and J. Širáň.

♦ ♦ ♦

Abstrakt:

The notion of a directed strongly regular graph was introduced by Duval as a possible generalization of classical strongly regular graphs. A directed strongly regular graph (DSRG) with parameters $(n,k,\mu,\lambda,t)$ is a regular directed graph on $n$ vertices with degree $k$ such that every vertex is incident with $t$ undirected edges, and the number of paths of length 2 directed from a vertex $x$ to a vertex $y$ is $\lambda$ if there is an arc from $x$ to $y$, and $\mu$ otherwise.

In this talk, first we repeat several feasibility conditions for parameter sets given by Duval. We will focus on a special case of DSRGs, namely, if $\lambda=0$ and $\mu=1$. Besides an infinite family of such DSRGs there are known just two more digraphs with these parameters: one of order 18, the second of order 108. The latter was just recently constructed by L. Jorgensen. We are also giving an explanation of these graphs in the terms of biaffine planes. Finally, we show how we obtained new DSRGs on 36 vertices from these digraphs using several different techniques (voltage assignments, mergings in association schemes) known from algebraic graph theory. (This is joint work with M. Klin, Ben Gurion University, Beer Sheva, Israel)

♦ ♦ ♦

Abstrakt:

A graph $G$ is equimatchable if every maximal matching of $G$ is maximum. It is known that any $2$-connected equimatchable graph is either bipartite or factor-critical. We prove that for any vertex $v$ of a $2$-connected factor-critical equimatchable graph $G$ and a minimal matching $M$ that isolates $v$ the graph $G-(M\cup v)$ is either $K_{2n}$ or $K_{n,n}$ for some $n$. We use this result to improve the upper bounds on the maximum size of $2$-connected equimatchable factor-critical graphs embeddable in the orientable surface of genus $g$ to $c\sqrt g+5$ if $g\ge 3$ where $c\le 12$ is constant for any fixed $g\ge 3$ and to $4\sqrt g+17$ if $g\le 2$. Moreover, for any nonnegative integer $g$ we construct a $2$-connected equimatchable factor-critical graph with genus $g$ and more than $4\sqrt{2g}$ vertices, which estabilishes that the maximum size of such graphs is $\Theta(\sqrt g)$. Similar bounds are obtained for nonorientable surfaces. In addition, we construct arbitrarily large $2$-connected equimatchable bipartite graphs with orientable genus $g$, and similar graphs with nonorientable genus $h$, for all nonnegative integers $g$ and $h$. Finally, we investigate planar $2$-connected factor-critical equimatchable graphs.

♦ ♦ ♦

Abstrakt:

We estimate the size of the neighbourhood of constant order $u$ in the interval graph of an $n$-ary random Boolean function. The interval graph is useful for finding a minimal DNF of a Boolean function. Its vertices correspond to maximal sub-cubes in the graph of a Boolean function, and two vertices are joined by an edge whenever the corresponding sub-cubes have a non-empty intersection. The neighbourhood of order $u$ of a given vertex is the set of all vertices whose minimal distance from the vertex is at most $u$. Our estimate on the size of the neighbourhood is approximately $n^{u.lg(log_{1/p}(n)}$ where $lg$ denotes the binary logarithm. So far, no reasonable bound of this parameter has been known.

♦ ♦ ♦

Abstrakt:

We estimate the minimum number of vertices of a cubic graph with given oddness and cyclic connectivity. We prove that a bridgeless cubic graph $G$ with oddness $\omega(G)$ other than the Petersen graph has at least $(5+1/4)\omega(G)$ vertices, and for each integer $k$ with $2\le k\le 6$ we construct an infinite class of cubic graphs with cyclic connectivity $k$ and small oddness ratio $|V(G)|/\omega(G)$. In particular, for cyclically $4$-connected snarks we improve the upper bound on oddness ratio to $13$ from the previously known bound of $15$, and for cyclically $6$-connected snarks we improve the ratio to $99$ from $118$. In addition, we construct a cyclically $4$-connected snark of girth $5$ with oddness $4$ on $44$ vertices, improving the best previous value of $46$.

♦ ♦ ♦

Abstrakt:

In this lecture we give a short survey of old and new results about branched coverings of graphs. This notion was introduced independently by many authors. Branched coverings of graphs are also known as harmonic maps or vertically holomorphic maps of graphs. The main idea of the present talk is to create a parallel between classical results on branched coverings of Riemann surfaces and those for graphs. We introduce the notion of a harmonic automorphism for a graph and discuss the Hurwitz upper bound on the number of harmonic automorphisms. Then we define a hyperelliptic graph as a two-fold branched covering of a tree. A few discrete versions of the Farkas and Accola theorems about hyperellipticity of coverings over genus two Riemann surface will be given.

♦ ♦ ♦

Abstrakt:

We survey results and open problems in hamiltonian graph theory centered around two conjectures of the 1980s that are still open: every 4-connected claw-free graph (line graph) is hamiltonian. These conjectures have lead to a wealth of interesting concepts, techniques, results and equivalent conjectures.

♦ ♦ ♦

Abstrakt:

We present a result of M. D. Hestenes and D. G. Higman from the paper "Rank $3$ Groups and Strongly Regular Graphs". Let $G$ be a strongly regular graph and let $x$ and $y$ be two arbitrary vertices from $G$. The authors show that for the ordered pair $[x,y]$ the number of different types of subgraphs of order $4$ that contain $x$ and $y$ only depends on whether $[x,y]$ is an edge or a non-edge. The problem is related to the study of properties of highly symmetric graphs.

♦ ♦ ♦

Abstrakt:

The minimum genus problem is a classical albeit NP-complete problem in topological graph theory. Minimum genus of cartesian products is closely related to the minimum genus of a group - the minimum among genera of all Cayley graphs of the given group. For abelian groups, the most difficult case arises when the group contains a Z_3 factor in its canonical decomposition. In this talk we focus mainly on the genus of $G_n$, the cartesian product of $n$ triangles, which is the Cayley graph of the direct product of $n$ copies of $Z_3$. Characteristic features of the problem of determining the genus of $G_n$ are a significant level of symmetry of the graphs, very large problem space, and absence of readily available methods.

In this talk we discuss several results on both lower and upper bounds on the genus of $G_n$, as well as computational aspects of the problem. Moreover, we introduce several new invariants - (strong) symmetric genus of a Cayley graph, genus range of a group, and (strong) symmetric genus of a group, and consider their relationship with the genus of $G_n$ and other known invariants.

This is a joint work with T. Pisanski.

♦ ♦ ♦

Abstrakt:

The weak 3-flow conjecture states that there exists a fixed integer k, such that each k-connected graph has a nowhere-zero 3-flow. We demonstrate the basic techniques that C. Thomasen used to prove this conjecture.

♦ ♦ ♦

Abstrakt:

Hovoríme, že vrchol x dominuje vrchol y ak je x=y alebo ak je xy hrana grafu. Nech je G graf a S je podmnožina jeho vrcholov. Potom S dominuje G efektívne, ak je každý vrchol grafu G dominovaný jediným vrcholom z S. Takáto efektívne dominujúca množina S je vlastne 1-kod.

Mobiov pásik $M_n$ je kubický graf, ktorý vznikne z kružnice na $2n$ vrcholoch pridaním perfektného párovania spájajúceho protiľahlé vrcholy kružnice. Využitím algebraického prístupu, pomocou liftov, sme dokázali, že súvislý kubický graf na 2^m vrcholoch nemá efektívnu dominančnú množinu jedine vtedy, keď je to Mobiov pásik.

Prezentované výsledky sú zo spoločnej práce s Primozom Potocnikom (Univ. Ljubljana).

♦ ♦ ♦

Abstrakt:

Pokrytie kružnicami resp. cyklami pre daný graf $G$ je taká množina kružníc $\mathcal{C}$ grafu $G$, že každá hrana $G$ je obsiahnutá aspoň v jednej kružnici z $\mathcal{C}$.

Signovaný graf je graf, ktorého každá hrana má znamienko + alebo -. Pre signované grafy rozlišujeme dva druhy kružníc balansovanú a nebalansovanú. Balansovaná (nebalansovaná) kružnica je taká, ktorá má párny (nepárny) počet znamienok. Preto je prirodzenou otázkou ako zadefinovať signovanú kružnicu, aby pokrytia signovanými kružnicami pre signované grafy boli nielen zovšeobecnením pokrytí kružnicami pre grafy, ale spĺňali aj ďalšie vlastnosti ako napríklad priamy súvis s nikde-nulovými tokmi. Odpoveď na túto otázku prichádza z Teórie matroidov.

Signovaná kružnica je balansovaná kružnica alebo tzv. nebalansovaná dvojkružnica, čo je súvislý signovaný graf pozostávajúci z dvoch dizjunktných nebalansovaných kružníc prepojených cestou. Pokrytie signovaného grafu signovanými kružnicami je potom taká množina signovaných kružníc, že každá hrana signovaného grafu je obsiahnutá aspoň v jednej z nich. V takomto prípade celopozitívny signovaný graf zodpovedá grafu bez znamienok, keďže neobsahuje nebalansovanú kružnicu a teda ani dvojkružnicu.

V prednáške okrem iného dokážeme, že ak má signovaný graf pokrytie signovanými kružnicami, potom existuje také pokrytie, že súčet dĺžok všetkých jeho signovaných kružníc je nanajvýš $11|E(G)|$. Navyše z dôkazu tvrdenia vyplýva, že každá hrana signovaného grafu je takýmto pokrytím pokrytá nanajvýš 11-krát.

Prezentované výsledky sú spoločnou prácou s E. Máčajovou, A. Raspaudom a M. Škovierom.

♦ ♦ ♦

Abstrakt:

Association schemes are one of the traditional areas of investigation in algebraic graph theory. Catalogues of all small association schemes are available from the website of Hanaki and Miyamoto. It is known that all association schemes of order up to 14 are Schurian, that is, they are coming from suitable transitive permutation groups in the standard manner. The first examples of non-Schurian association schemes exist on 15, 16, and 18 vertices. In particular, there are only two examples of non-Schurian association schemes of order 18.

Starting from a successful computer-free interpretation of these two examples, and using extensive computer algebra experimentation in conjunction with further reasoning, we are able to show the existence of at least four infinite families of non-Schurian association schemes of order 2p^2 (for p prime, p>3).

In this lecture I will start from a consideration of the two initial examples on 18 points, and describe some auxiliary coherent configurations. Then the four infinite families of association schemes will be presented. We will discuss some of their properties, as well as their links with certain known objects in extremal graph theory, for example with McKay-Miller-Siran graphs.

This is joint work with M. Klin.

♦ ♦ ♦

Abstrakt:

Association schemes are one of the traditional areas of investigation in algebraic graph theory. In this talk we give a short introduction to the concept of association schemes. These objects could be independently defined in the language of matrices, binary relations, or color graphs. A significant family of association schemes, so-called Schurian association schemes, can be constructed from transitive permutation groups. More interesting association schemes are those which cannot be obtained in this manner. We will also associate three more groups with an association scheme: its combinatorial group of automorphisms, group of color automorphisms, and the group of algebraic automorphisms.

♦ ♦ ♦

Abstrakt:

Every vertex $v$ in a connected $2d$-regular graph $G$ divides any eulerian trail $T$ into $d$ closed subtrails $T_1,T_2,...,T_d$ based at $v$. If $G$ has odd order, the number of edges of $G$ is $d$ times an odd number, so one may ask whether $T$ and $v$ can be chosen in such a way that all the subtrails $T_i$ have odd length. The answer is trivially positive for $d=1$, and is positive also for $d=2$. We show that for $d=3$ the answer is again positive, and explain why this case is important for determining the flow number of an arbitrary signed eulerian graph. Our methods extend to proving more general results about decompositions of eulerian graphs into two or three closed trails of odd length based at the same vertex under similar assumptions.

This is a joint work with Edita Mačajová.

♦ ♦ ♦

Abstrakt:

Blíži sa 50-te výročie vôbec prvej skutočne významnej medzinárodnej konferencie z teórie grafov v Smoleniciach. Zborník z tejto konferencie je dodnes významným zdrojom zásadných článkov a problémov z tejto oblasti. V prednáške sa budeme zaoberať dvoma takýmito dodnes otvorenými problémami, ktoré na konferencii sformuloval Gerhard Ringel, respektíve Anton Kotzig.

♦ ♦ ♦

Abstrakt:

Pozoruhodným rysem věty o čtyřech barvách je značný počet jejích ekvivalentních formulací, z nichž některé se na první pohled týkají rovinných grafů nebo barevnosti pouze okrajově. Přednáška bude věnována souvislosti této věty s teorií uzlových invariantů určených Lieovými algebrami. Připomeneme také Penroseův kalkulus tenzorových diagramů, na který zmíněná teorie navazuje. S tématem je úzce spjat Penroseův polynom, o jehož definici a známých vlastnostech se rovněž zmíníme. Přednáška bude pojata jako úvod do této oblasti a nepředpokládá hlubší algebraické znalosti.

♦ ♦ ♦

Abstrakt:

A circuit cover of a graph $G$ is a collection $\mathcal{C}$ of circuits such that each edge of $G$ belongs to at least one circuit from $\mathcal{C}$. There is a natural analogue of this concept for signed graphs, graphs where each edge is either positive or negative. As suggested by matroid theory, a signed circuit is either a single circuit with an even number of negative edges, or a pair of disjoint circuits with an odd number of negative edges each, joined with a path. It can be shown that a signed graph has a circuit cover if and only if it admits a nowhere-zero integer flow. In the talk we will mention several bounds on the length of a shortest circuit cover in a signed graph $G$, depending on the existence of a nowhere-zero $k$-flow in $G$. In particular we show that a signed graph $G$ that admits a nowhere-zero $2$-flow has a circuit cover with total length at most $\frac{4}{3}\cdot |E(G)|$. This bound is tight for infinitely many graphs.

This is a joint work with Edita Máčajová, Andre Raspaud a Martin Škoviera.

♦ ♦ ♦

Abstrakt:

Cieľom prezentácie je popísať vzťahy medzi intervalovým grafom boolovskej funkcie, skrátenou disjunktívnou normálnou formou a minimálnou disjunktívnou normálnou formou tejto funkcie.

♦ ♦ ♦

Abstrakt:

A remarkable but widely unknown theorem of Beckman and Quarles (1954) states that if a map f of R^d (d>1) into itself preserves unit distance (i.e. for any x,y in R^d, dist(x,y) = 1 implies dist(f(x),f(y)) = 1), then f is an isometry. Does this property also hold when one considers unit-distance preserving selfmaps of rational euclidean space Q^d? The talk will explore some relations of the Beckman-Quarles theorem with colouring and connectivity problems in metric graph theory.

♦ ♦ ♦

Abstrakt:

Many people have already encountered the Fifteen Puzzle. The child game with the goal to order fifteen labeled blocks placed in the square of size four times four, where one position is empty. The notoriety of the puzzle derives from the impossibility of being able to swap the positions of 14 and 15. One possible representation of the $n$-Puzzle is a graph on $n+1$ vertices (one for every labeled block and one for the empty space). The edges of the graph will present the neighborhood of blocks. Rick Wilson's theorem states that (apart from simple polygons, nonseparable graphs and the graph that is the subject of our talk) the group of permutations of attainable positions is either $S_n$, if the graph contains some odd circuits, or $A_n$ in the other case. It is easy to see that the graph of the Fifteen Puzzle is bipartite, so it contains only even circuits. The exception of the theorem above is the graph with seven vertices, one $6$-circuit and two $5$-circuits. What then is the automorphism group of this Tricky Six Puzzle? A paper of A. Fink and R. Guy (Math. Magazine, 2009) gives an answer to this question and shows the relationship of this special case with other mathematical problems.

♦ ♦ ♦

Abstrakt:

While maps are cellular embeddings of connected graphs on connected compact surfaces, hypermaps are cellular embeddings of hypergraphs. Regular oriented maps/hypermaps can be chiral (if the full automorphism group contains no "reflections") or not. Chiral hypermaps can appear with different chirality indices; while low chiral hypermaps are abundant, extreme hight chiral maps/hypermaps (totaly chiral) seems to be very rare. In this talk we speak, among other things, on several forms of regularity and chirality of maps/hypermaps, how restrict regularity can encodes a hypermap (hypermaps are restricted form of maps) and how regular direct abstract polytopes can be encoded on compact surfaces as restrictedly regular hypermaps.

♦ ♦ ♦

Abstrakt:

V doteraz publikovaných prácach sme ukázali, že existuje až n^{an^2} triangulácií plôch grafom K_n (ako orientovateľných tak aj neorientovateľných), kde a je kladná konštanta. Bohužiaľ, trieda radov n bola veľmi "riedka". V súčasnosti sa nám podarilo zostrojiť takéto triangulácie pre podstatne hustejšie triedy n.

V prípade neorientovateľných plôch máme dokonca lineárnu triedu a výsledok je založený na bi-vnoreniach Cayleyho tabuliek dihedrálnych grúp. Tieto bi-vnorenia boli zostrojené ad-hoc.

V prípade orientovateľných plôch máme "skoro" lineárnu triedu, ktorú sme zostrojili pomocou bi-vnorení Latinských štvorcov, z ktorých jeden je Cayleyho tabuľkou metacyklickej grupy. Tento prístup je oveľa zaujímavejší a práve o ňom bude príspevok. Využívame tu skutočnosť, ze Cayleyho tabuľka metacyklickej grupy má pre isté rády n "veľmi veľa" latinských podštvorcov.

♦ ♦ ♦

Abstrakt:

A (k+1)-colouring sequence of a graph G is an ordering of its vertices into a sequence v_1, v_2, ... , v_n such that every vertex v_i has at most k neighbours which are in front of it in the sequence. This equivalently means that G is k-degenereted and that G has colouring number k+1.

Since every planar graph has a vertex of degree 5 or less, every planar graph has a 6-colouring sequence. We will show that every planar graph has a 4-colouring sequence of size at least 8/9.|V(G)|. We conjecture that every planar graph has a 4-colouring sequence of size at least 11/12.|V(G)|.

♦ ♦ ♦

Abstrakt:

According to a folklore result, every regular map on an orientable surface with abelian automorphism group belongs to one of three infinite families of maps with one or two vertices. Here we deal with regular maps whose automorphism group is nilpotent. We show that each such map decomposes into a direct product of two maps $H\times K$, where Aut$(H)$ is a $2$-group and $K$ is a map with a single vertex and an odd number of semiedges. Many important properties of nilpotent maps follow from this decomposition. We show, for example, that apart from two well defined classes of maps on at most two vertices and their duals, every nilpotent regular map has both its valency and face-size divisible by $4$. We give a complete classification of nilpotent regular maps of nilpotency class $2$ and $3$, and prove that for every integer $c\ge 1$ there are only finitely many simple regular maps whose automorphism group is nilpotent of class $c$.

♦ ♦ ♦

Abstrakt:

Ako opak problému stupňa a priemeru sa zaoberáme minimálnym počtom vrcholov, ktoré môže mať graf daného stupňa a priemeru. Zatiaľ čo pre pravidelné grafy je problém veľmi jednoduchý, pre vrcholovo-tranzitívne je celkom zaujímavý. Napriek tomu dávame takmer vo všetkých prípadoch optimálne riešenie.

♦ ♦ ♦

Abstrakt:

An oriented map is a connected graph embedded into an oriented surface surface in such a way that the resulting faces are simply connected (homeomorphic to an open disk). The $j$-th hole operator $H_j$ creates a new map ${\cal M}^{H_j}$ from an oriented map ${\cal M}$ such that the faces of ${\cal M}^{H_j}$ are the $j$-th holes of ${\cal M}$, that is, cyclic sequences of edges, each two consecutive sharing a vertex, so that at each vertex, the adjacent edges subtend $j$ faces on the right. The map ${\cal M}^{H_j}$ is well defined whenever the valency of the map ${\cal M}$ is coprime to $j$. These were introduced by Steve Wilson in 1979.

The operator $H_{-1}$ has always been regarded as to produce the mirror image and when restricted to the class of $n$-valent maps, $H_{j}$ has been identified with the operator $H_{ j \pmod n}$. But ... is this really the case?

♦ ♦ ♦

Abstrakt:

The connection between the existence of a an orbit of a skew-morphism that is closed under inverses and generates the whole group and the existence of a regular Cayley map is by now a firmly established part of the theory of regular Cayley maps. In our talk, we investigate the role of those orbits of skew-morphisms that do not give rise to regular Cayley maps because they are not closed under inverses. We use the term half-regular map to describe an orientable map with an orientation preserving automorphism group that is transitive on vertices and half-transitive on darts. We present a full classification of half-regular Cayley maps and argue that half-regular Cayley maps come in two types: those that arise from two skew-morphism orbits of equal size that are both closed under inverses and those that arise from two equal-sized orbits that do not contain involutions or inverses but one contains the inverses of the other. In addition, half-regular Cayley maps of the first type are shown to be half-edge-transitive, while half-regular Cayley maps of the second type are shown to be necessarily edge-transitive. A connection between half-regular Cayley maps and regular hypermaps is also investigated.

The results come from a joint project with Roman Nedela.

♦ ♦ ♦

Abstrakt:

A cycle double cover of a cubic graph G is a set S of cycles of G such that every edge of G is contained in exactly two cycles of S. There are several variations of the cycle double cover conjecture (CDCC). We introduce a new one which we call the Strong 5-CDCC. We prove several new results which are related to this conjecture.

♦ ♦ ♦

Abstrakt:

Graf nazveme "equimatchable", ak v ňom každé dve nerozšíriteľné párenia majú rovnakú mohutnosť. V prednáške sa budeme zaoberať vlastnosťami chordálnych equimatchable grafov a equimatchable karteziánskych súčinov grafov. Ukážeme, že pre každý equimatchable chordálny graf $G$ existuje graf $H$ taký, že $H\# T$ je izomorfný s $G$ pre každú kostru $T$ grafu $H$, kde $H\# T$ je prienikový graf fundamentálnych cyklov grafu $H$ vzhľadom na kostru $T$. Predstavíme charakterizáciu dvojsúvislých grafov $H$, pre ktoré platí, že $H \# T$ je equimatchable pre každú kostru $T$ grafu $H$. Pre súvislé karteziánske súčiny grafov ukážeme, že jediný equimatchable netriviálny karteziánsky súčin je $K_2 \square K_2$. V záverečnej časti sa zameriame na zovšeobecnenie pojmu rozšíriteľnosti párení v karteziánskych grafoch a ukážeme niektoré vlastnosti všeobecnejšej rozšíriteľnosti.

♦ ♦ ♦

Abstrakt:

The circular chromatic index of a graph G is the infimum of all rational numbers p/q, for p and q coprime, such that there exists a circular p/q-edge-coloring of the graph G. It is an interesting problem to determine which possible values of the circular chromatic index are attained for d-regular graphs with chromatic index d + 1 (known as d-regular snarks). In this talk we provide a construction of 4-regular snarks which shows that all the values 4 + 2/r for an integer r > 8 are attained as circular chromatic indices. So far, no such class of graphs has been known.

♦ ♦ ♦

Abstrakt:

A map M is edge-transitive if its group of automorphisms, Aut(M), acts transitively on the edges. Let M be an edge-transitive map. Maps M and their medial maps Med(M) are in a one-to-one correspondence, hence we may classify edge-transitive maps on orientable surfaces by employing well-developed techniques of the classification of orientable vertex-transitive maps.

Since the orientation-preserving automorphism group of a medial map is of index at most two in the automorphism group of a medial map, we know, that the quotient of the medial map of orientable edge-transitive map has at most two vertices. Orientation-preserving automorphisms of an edge-transitive map are *face colour-preserving*, i.e. they cannot act as a duality in the medial map. The number of possible quotient maps significantly decreases, in particular there are just six quotient maps to consider. In the case of two-vertex quotient, $\bar{M}$, of a medial map, $M$, the automorphism group of the respective (medial) map must contain an automorphism $\phi$, such that $\phi$ projects onto an automorphism of the quotient, transposing the two vertices of $\bar{M}$ and preserving the face-colouring of $\bar{M}$. These conditions gives to rise to \emph{seven} infinite families of edge-transitive maps, up to duality. Using the technique of voltage assignments we can reconstruct all edge-transitive maps of given genus or with given number of edges.

♦ ♦ ♦

Abstrakt:

We consider the following problem: Given a set of points S in the Euclidean plane (representing e.g. sensors in a sensor network), number of antennae k per point, a transmission range r and a transmission angle phi, set the transmission direction for each antenna in such a way that the resulting directed graph is strongly connected.

We provide various upper and lower bounds on r with respect to k and phi and show that for k=2 and transmission angle at most alpha it is NP-hard to approximate the optimal radius to within a factor of x, where x and alpha are the solutions of equations x = 2 sin(alpha) = 1 + 2 cos(2*alpha).

♦ ♦ ♦

Abstrakt:

A snark is a cubic graph with no $3$-edge-colouring. In 1996, Nedela and Skoviera proved the following theorem: Let $G$ be a snark with an $n$-edge-cut, $n\geq 2$, whose removal leaves two $3$-edge-colourable components $M$ and $N$. Then both $M$ and $N$ can be completed to two snarks $\tilde M$ and $\tilde N$ of order not exceeding that of $G$ by adding at most $\kappa(n)$ vertices, where the number $\kappa(n)$ only depends on $n$. The known values of the function $\kappa(n)$ are $\kappa(2)=0$, $\kappa(3)=1$, $\kappa(4)=2$ (Goldberg, 1981), and $\kappa(5)=5$ (Cameron, Chetwynd, Watkins, 1987). The value $\kappa(6)$ is not known and is apparently difficult to calculate. In 1979, Jaeger conjectured that there are no 7-cyclically-connected snarks. If this conjecture holds true, then $\kappa(6)$ is the last important value to determine. Our talk is aimed attacking the problem of determining $\kappa(6)$ by investigating the structure and colouring properties of potential complements in 6-decompositions of snarks. We find a set of $14$ complements which suffice to perform $6$-decompositions of snarks with at most $30$ vertices. We show that if this set is not complete to perform $6$-decompositions of all snarks, then $\kappa(6)\geq 20$ and there are strong restrictions on the structure of (possibly) missing complements.

Part of the proofs are computer assisted.

♦ ♦ ♦

Abstrakt:

A $(k,g)$-cage is a $k$-regular graph of girth $g$ and smallest possible order. Although studied for over 50 years now, the problem of finding cages for any given pair of parameters $(k,g)$ has only been solved for a very limited set of parameters, and is generally deemed to be very hard.

The idea of relaxing the restrictions and allowing for bi-regular graphs - graphs with exactly two different degrees - for any given girth was therefore introduced with the hope of providing further insights and possible breakthroughs. In our talk, we show that the problem of finding bi-regular cages is indeed solvable, and present a construction that produces bi-regular cages for almost all sets of admissible parameters.

We will conclude our talk by examining the question of whether our solution constitutes a dead end or a detour from the original hopes for cracking the classical cage problem; hopefully with some help from the audience.

The presented results come from our joint work with Prof. Geoff Exoo, and have a significant computational component.

♦ ♦ ♦

Abstrakt:

Grafové uzávěry umožňují často podstatným zpusobem zjednodušit strukturu grafu při zachování některé jeho zvolené vlastnosti (zpravidla hamiltonovského typu), a staly se tak zejména v poslední době duležitým nástrojem hamiltonovské teorie grafu. V prednášce ukážeme hlavní myšlenky konstrukce některých grafových uzávěru pro grafy bez K_{1,3} a techniky, jež umožňují po redukci problému na hranové grafy daný problém transformovat do třidy kubických grafu, s aplikací na konkrétní případ uzávěru pro hamiltonovskou souvislost a jejich použití při odvození asymptoticky ostré podmínky Oreho a Diracova typu pro hamiltonovskou souvislost v grafech bez K_{1,3}.

♦ ♦ ♦

Abstrakt:

Lovasz and Plummer conjectured in the 1970's that cubic bridgeless graphs have exponentially many perfect matchings. This conjecture has been verified for bipartite graphs by Voorhoeve in 1979, and for planar graphs by Chudnovsky and Seymour in 2008. Then several general lower bounds for the number of perfect matchings in cubic bridgeless graphs appeared, and finally, the conjecture has been settled recently. In this talk, a survey on methods used to attain these results is provided.

♦ ♦ ♦

*S(2,1)*-hrátky so zovšeobecnenými Blanušovými snarkami"

Abstrakt:

*r-S(2,1)*-ohodnotenie grafu *G* je zobrazenie z množiny vrcholov *V(G)* grafu *G* do cyklickej grupy *Z _{r}* rádu

*r*, spĺňajúce dve podmienky. Po prvé, každá dvojica vrcholov spojených cestou dĺžky 1 v

*G*(susedov v

*G*) má hodnoty vo vzdialenosti aspoň 2 v

*Z*. Po druhé, každá dvojica vrcholov spojených cestou dĺžky 2 v

_{r}*G*(so spoločným susedom v

*G*) má hodnoty vo vzdialenosti aspoň 1 v

*Z*(rôzne v

_{r}*Z*). σ-číslo σ

_{r}*(G)*grafu

*G*je najmenšie kladné celé číslo

*r*, pre ktoré existuje

*r-S(2,1)*-ohodnotenie

*G*.

Zovšeobecnené Blanušove snarky

*B*prvého a

^{1}_{m}*B*druhého typu rádu

^{2}_{m}*8m+10*tvoria nekonečné triedy kubických grafov s chromatickým indexom 4 (snarkov). Nultým členom

*B*a

^{1}_{0}*B*je Petersenov graf. Prvým členom

^{2}_{0}*B*je prvý Blanušov snark a

^{1}_{1}*B*je druhý Blanušov snark.

^{2}_{1}Určíme σ-číslo zovšeobecnených Blanušových snarkov.

♦ ♦ ♦

Abstrakt:

A locally maximal embedding of a graph *G* is a cellular embedding of *G* on an orientable surface such that every vertex of *G* is incident with at most two faces. These are precisely the embeddings whose genus cannot be raised by moving any edge in the local rotation at one of is end-vertices. The locally maximal genus of a graph *G* is the minimum genus of a locally maximal embedding of *G*. Among other results we show how to calculate the locally maximal genus of many interesting classes of graphs, for example completegraphs, complete bipartite graphs and hypercubes. We investigate the relationships between locally maximal genus, minimum genus, and maximum genus. In particular, we provide results towards a classification of all graphs with locally maximal genus equal to minimum genus.

Joint work with M. Škoviera.

♦ ♦ ♦

Abstrakt:

We study the interplay between the maximum genus of a graph and bases of its cycle space via the corresponding intersection graph. Our main results show that the matching number of the intersection graph is independent of the basis precisely when the graph is upper-embeddable, and completely describe the range of matching numbers if the graph is not upper-embeddable. Particular attention is paid to cycle bases consisting of fundamental cycles with respect to a given spanning tree. For 4-edge-connected graphs, the intersection graph with respect to any spanning tree (and, in fact, with respect to any basis) has either a perfect matching or a matching missing exactly one vertex. We show that if a graph is not *4*-edge-connected, different spanning trees may lead to intersection graphs with different matching numbers. We also show that there exist *2*-edge-connected graphs for which the set of values of matching numbers of their intersection graphs contains arbitrarily large gaps.

♦ ♦ ♦

Abstrakt:

Mathematical models of fullerenes are cubic spherical maps of type $(5;6)$, that is, with pentagonal and hexagonal faces only. Any such map necessarily contains exactly 12 pentagons, and it is known that for any integer $\alpha\ge 0$ except $\alpha=1$ there exists a fullerene with precisely $\alpha$ hexagons.

In this talk we consider hyperbolic analogues of fullerenes, modelled by cubic maps of face-type $(6; k)$ for some $k\ge 7$ on orientable surface of genus at least two. The number of $k$-gons in this case depends on the genus but the number of hexagons is again independent of the surface. We focus on the values of $k$ that are `universal' in the sense that there exist cubic maps of face-type $(6; k)$ for all genera $g\ge 2$. By Euler's formula, if k is universal, then $k\in\{7; 8; 9; 10; 12; 18\}$.

We show that for any $k\in\{7; 8; 9; 12; 18\}$ and any $g\ge 2$ there exists a cubic map of face-type $(6; k)$ with any prescribed number of hexagons. For $k = 7$ and 8 we also prove the existence of polyhedral cubic maps of face-type $(6; k)$ on surfaces of any prescribed genus $g\ge 2$ and with any number of hexagons $\alpha$, with possible exceptions when $k = 8$ and either $g = 2$ and $\alpha= 4$, or else $g = 3$ and $\alpha= 1; 2$.

Joint work with P. Potocnik, J. Siran, and R. Skrekovski.

♦ ♦ ♦

Abstrakt:

We consider the following problem. Let $S$ be a set of $2$-connected cubic graphs. Which properties must $S$ have so that every $3$-connected cubic graph $G$ has a matching $M$ such that every component of $G-M$ is either an even circuit or a subdivision of a graph of $S$ with an even number of subdivision vertices? We present some answers to this question and disprove a conjecture of H\"aggkvist and Markstr\"om which is related to the Cycle Double Cover Conjecture.

♦ ♦ ♦

Abstrakt:

To each unoriented edge $e$ of a connected graph $X$ we assign an element $\zeta_e$ from a given abelian group $\Gamma$. The graph $X(\Gamma,\zeta)$ with $V(X) \times \Gamma$ as the vertex set, where $(u,g)$ and $(v,h)$ are adjacent whenever there is an edge $e = uv$ in $X$ and $g+h = \zeta_e$, is called a crosscover. Crosscovers, an obvious generalization of Cayley sum graphs, are a special kind of covers. Some basic facts like regularity/irregularity, connectedness, and lifting automorphisms will be discussed.

(Joint work with Steve Wilson.)

♦ ♦ ♦

Abstrakt:

Opíšeme transformácie regulárnych máp na orientovateľných plochách, ktoré zachovávajú plochu a akciu grupy automorfizmov pôvodnej mapy. Aplikácia týchto transformácií je ekvivalentná (v niektorých) prípadoch dobre známym geometrickým transformáciám máp - trunkácii, mediálu, duálu mapy atď.

Definujeme 10 transformácií regulárnym máp, pričom v piatich prípadoch vedie transformácia regulárnej mapy M priamo na vrcholovo tranzitívnu mapu N. V ďalších piatich prípadoch je akcia grupy automorfizmov na výslednej mape N vrcholovo tranzitívna jedine vtedy, ak mala pôvodná (regulárna) mapa M navyše aj ďalšie, vonkajšie symetrie, ktoré dokážeme charakterizovať. V týchto prípadoch aktuje pôvodná grupa automorfizmov G mapy M na vrcholoch mapy N s dvomi orbitmi a grupa G, rozšírená o vonkajší automorfizmus mapy M, má akciu s jedným orbitom na vrcholoch mapy N.

Je veľmi dobre známym faktom, že grupa orientáciu zachovávajúcich automorfizmov regulárnej mapy M je kvocientom grupy C * C_2. Ukážeme, že pokiaľ je vrcholovo tranzitívna mapa jednoduchá a pripúšťa akciu kvocientu C * C_2, potom je buď regulárna alebo ju možno transformovať z regulárnej mapy použitím jednej z 10 transformácií. Klasické znalosti a klasifikácie Platónskych a Archimedovských telies je možné rozšíriť použitím transformácií na plochy tých rodov, pre ktoré poznáme zoznam regulárnych máp.

♦ ♦ ♦

Abstrakt:

V roku 1890 Heawood sformuloval hypotézu, ktorá stanovovala minimálny počet farieb, pomocou ktorých vieme korektne zafarbiť každý graf vnoriteľný do (orientovateľnej) uzavretej a kompaktnej plochy. Táto hypotéza bola dokázaná v roku 1968 Ringelom a Youngsom, ktorí našli pre každé prípustné *n* jednu trianguláciu grafom *K _{n}*. Neskôr sa ukázalo, že takýchto triangulácií je podstatne viac. V prednáške referujeme o metódach, pomocou ktorých sme dokázali, že takýchto triangulácií je $n^{an^2}$ a to pre lineárne triedy

*n*(v prípade neorientovateľných vnorení) a pre "skoro-lineárne" triedy (v prípade orientovateľných vnorení). Sústredíme sa práve na orientovateľné vnorenia.

♦ ♦ ♦

Abstrakt:

Ukážeme viacero možností ako skonštruovat Hoffmanov-Singletonov graf. Ako aplikáciu dokážeme, že jeho grupa automorfizmov obsahuje podgrupu izomorfnú s grupou A_7.

♦ ♦ ♦

Abstrakt:

The Hoffman-Singleton graph is the biggest known Moore graph. Following the article "The Hoffman-Singleton Graph and its Automorphisms" by Paul R. Hafner we look at the structure of this graph. As the abstract of the article says "We describe the Hoffman-Singleton graph geometrically, showing that it is closely related to the incidence graph of the affine plane over Z_5. This allows us to construct all automorphisms of the graph."

♦ ♦ ♦

Abstrakt:

The concept of a nowhere-zero flow on a bidirected graph is a natural generalisation of a nowhere-zero flow on a directed graph. A bidirected graph is a graph where edges are divided into half-edges and each half-edge has an independent orientation. The flow number of a bidirected graph $G$ is the smallest integer $k$ such that $G$ admits a flow with values in the set $\{\pm 1,\pm 2,\ldots,\pm(k-1)\}$. Unlike the directed case, where a graph has a nowhere-zero flow if and only if it is bridgeless, in the bidirected case no such simple condition is available.

In this talk we determine the flow number of bidirected complete and complete bipartite graphs. We show that, if one of such graphs admits a nowhere-zero flow, then it admits a nowhere-zero 4-flow and we characterize which of these graphs have the flow number 2 or 3.

♦ ♦ ♦

Abstrakt:

The order of a graph of maximum degree $d$ and diameter $2$ cannot exceed $d^2+1$, the Moore bound for diameter two. A combination of known results\ guarantees the existence of regular graphs of degree $d$, diameter $2$, and order at least $d^2-2d^{1.525}$ for all sufficiently large $d$, asymptotically approaching the Moore bound. The corresponding graphs, however, tend to have a fairly small or trivial automorphism group and the nature of their construction does not appear to allow for modifications that would result in a higher level of symmetry. The best currently available construction of vertex-transitive graphs of diameter $2$ and preassigned degree gives order $\frac{8}{9}(d+\frac{1}{2})^2$ for all degrees of the form $d=(3q-1)/2$ for prime powers $q\equiv 1$ mod $4$.

We show that for an infinite set of degrees $d$ there exist Cayley, and hence vertex-transitive, graphs of degree $d$, diameter $2$, and order $d^2-O(d^{3/2})$.

♦ ♦ ♦

Abstrakt:

The Hamming graph *H(d,q)* has vertex set the set of ordered d-tuples of elements of *{1,2,...,q}*, two vertices being adjacent if they differ in precisely one coordinate.

We will study the subgraph *I(d,q)* of the Hamming graph *H(d,q)* induced by the set of *d*-tuples with pairwise disjoint coordinates. In particular we completely determine which graphs *I(d,q)* are Cayley.

♦ ♦ ♦

*K*"

_{2}Abstrakt:

*r-L(2,1)-ohodnotenie* grafu je zobrazenie z vrcholovej množiny grafu do množiny nezáporných celých čísel {0,1, ...,r} také, že dvojicu susedných vrcholov zobrazí na celé čísla s rozdielom aspoň 2 a dvojicu vrcholov so spoločným susedom zobrazí na rôzne celé čísla. *λ-číslo* grafu je najmenšie *r* také, že graf má *r-L(2,1)*-ohodnotenie.

Vrcholová množina skúmaných súčinov grafov je karteziánskym súčinom vrcholových množín činiteľov, hranová množina závisí od typu súčinu. *Priamy súčin G _{1} x G_{2}* grafov

*G*a

_{1}*G*má hranu, ak sú hrany v činiteľoch v oboch súradniciach.

_{2}*Karteziánsky súčin G*grafov

_{1}G_{2}*G*a

_{1}*G*má hranu, ak je hrana v činiteli v jednej zo súradníc a zároveň rovnosť v druhej zo súradníc.

_{2}*Silný súčin*grafov

*G*a

_{1}*G*má hranu, ak je hrana v priamom súčine alebo ak je hrana v karteziánskom súčine.

_{2}Hornými ohraničeniami λ-čísla súčinov grafov s maximálnym stupňom oboch činiteľov aspoň 1 sa zaoberali napríklad Shao a Yeh (2005) pre kareziánsky súčin a Klavžar a Špacapan (2005) a Shao et al. (2007) pre priamy a silný súčin. Autorom sa podarilo dosiahnuť lepšie ohraničenia, ak navyše predpokladali, že maximálny stupeň oboch činiteľov je aspoň 2. Ak mal aspoň jeden z činiteľov maximálny stupeň 1, zostali v platnosti horšie ohraničenia. λ-číslo súčinu s jedným z činiteľov s maximálnym stupňom 1 je rovné λ-číslu súčinu druhého z činiteľov a kompletného grafu

*K*. To nás motivovalo skúmať ohraničenia λ-čísla súčinov s činiteľom

_{2}*K*.

_{2}V tejto prednáške uvedieme operácie na grafe

*G*použité na stanovenie horného ohraničenia λ-čísla priameho, karteziánskeho a silného súčinu G a kompletného grafu

*K*, samotné ohraničenia a ich porovnanie s pôvodnými ohraničeniami.

_{2}

♦ ♦ ♦

Abstrakt:

A real flow on a graph is a flow with values in $\mathbb{R}$. A real nowhere-zero $r$-flow is a real flow~$\phi$ with each edge satisfying the condition $1\leq|\phi (e)|\leq r-1$. The real flow number $\Phi_{\mathbb{R}}(G)$ of a graph $G$ is the infimum of all reals $r$ such that $G$ has a real nowhere-zero $r$-flow.

In this talk we present methods that can be used to determine real flow numbers of graphs, with focus on cubic graphs. Using these methods we prove that the real flow number of all generalized Blanuša snarks except for the Petersen graph is 4.5.

♦ ♦ ♦

Abstrakt:

For a digraph *D*, the domination number of *D* is denoted by *γ(D)*, the total domination number of *D* is denoted by *γ _{t}(D)*, and the digraph obtained by reversing all the arcs of

*D*is denoted by

*D*.

^{-}We show that the difference $γ(D

^{-})-γ(D) can be arbitrarily large in the class of 2-regular strongly connected digraphs, and similarly,

*γ*can be arbitrarily large in the class of 3-regular strongly connected digraphs. The similar results for larger valencies were proved by Knor and Niepel. We also show that every 2-regular digraph

_{t}(D^{-})-γ_{t}(D)*D*satisfies

*γ*.

_{t}(D)=γ_{t}(D^{-})This completes the solutions of Problems~1 and 2 posed by Knor and Niepel.

♦ ♦ ♦

Abstrakt:

In this talk we discuss the problem of determining the maximum integer *k* such that a given graph has an embedding into the orientable surface of genus *k*. This integer is known as the maximum genus of a graph and can be characterised combinatorially, without referring to surfaces. Using such characterisations, we derive three types of results. First, we present a new simple 2-approximation algorithm for the maximum genus. Second, we show that the maximum genus can provide both lower and upper bound on the maximum number of pairwise vertex-disjoint cycles of a graph. Finally, we show how one can easily obtain lower and upper bounds on the maximum genus of graphs from particular classes, for example, graphs with fixed girth and minimum degree.

♦ ♦ ♦

Abstrakt:

A signed graph is a graph in which every edge is labelled with a sign, + or -. In the talk we introduce flows on signed graphs as a natural analogue of flows on unsigned (that is, all-positive) graphs, based on the use of bidirected rather than directed edges. After giving a brief survey of known results about nowhere-zero flows on signed graphs we concentrate on flows on signed eulerian graphs. We show that every signed eulerian graph that has a nowhere-zero flow has a nowhere-zero 4-flow. This indicates a significant difference from the unsigned case where every eulerian graph is known to have a nowhere-zero 2-flow. We also characterise those signed eulerian graphs whose flow number equals 2, 3, and 4, respectively.

This is a joint work with Edita Macajova.

♦ ♦ ♦

Abstrakt:

An undirected graph *G* with a diameter *k* is said to be goal-minimally *k*-diametric (*k*-GMD for short) if for every edge *uv* of *G* the distance *d _{G-uv}(x,y)* is greater than

*k*if and only if

*{x,y}={u,v}*. We show how to obtain infinitely many 6-GMD and 8-GMD graphs from a construction which is a generalization of Plesník's construction of 6-GMD graphs. This construction is similar to the O'Keefe-Wong construction of cages.

This is a joint work with Beáta Štupáková.

♦ ♦ ♦

Abstrakt:

Silne regulárny graf s parametrami *v*, *k*, *λ* a *μ*, skrátene *SRG(v,k,λ,μ)* je *k*-regulárny graf na *v* vrcholoch taký, že ľubovoľné dva susedné vrcholy majú práve *λ* spoločných susedov a ľubovoľné dva nesusedné vrcholy majú práve *μ* spoločných susedov.

V prednáške predstavíme niekoľko problémov, s ktorými sa môžeme stretnúť pri hľadaní silne regulárnych grafov s "rozumne veľkou" grupou automorfizmov.

♦ ♦ ♦

Abstrakt:

r-S(2,1)-farbenie grafu je vrcholové farbenie prvkami cyklickej grupy Z_r také, že susedné vrcholy sú zafarbené farbami vo vzdialenosti aspoň 2 v Z_r a vrcholy vo vzdialenosti 2 sú zafarbené rôznymi farbami. Vzdialenosti farieb v Z_r meriame prirodzenou cirkulárnou metrikou. Najmenšie r, pre ktoré má graf r-S(2,1)-farbenie, sa nazýva sigma-číslo grafu. V prednáške sa budeme zaoberať S(2,1)-farbením grafov, ktoré vznikajú z určitého počtu izomorfných segmentov cyklicky zoradených tak, aby otočenie o jeden segment bolo automorfizmom výsledného grafu. Základom nášho prístupu k S(2,1)-farbeniu týchto grafov je nájdenie všetkých r-S(2,1)-farbení vhodného podgrafu a ich následné pospájanie do r-S(2,1)-farbenia celého grafu. Hlavným problémom pri tomto postupe sa ukazuje byť veľkosť množiny všetkých r-S(2,1)-farbení podgrafu, čo riešime ich rozdelením do orbít vzhľadom na nejakú grupu automorfizmov, analýzou matice susednosti prechodového grafu farbení alebo použitím vhodného napäťového grafu.

♦ ♦ ♦

Abstrakt:

We present a general result about weighted matroids which has many interesting corollaries. The first corollary is a special case of a conjecture on cyclic orderings of matroids, the second one proves a conjecture of Goncalves and the third one is a generalization of a result of Nash-Williams on disjoint spanning trees in graphs for matroids. Another corollary is the equality of circular and fractional arboricity of matroids.

The talk is divided into two parts. In the first part we introduce matroids and the basic concepts of matroid theory: independence, basis, rank, and duality of matroids. Then we present certain conjectures on cyclic orderings and arboricity of matroids. The second part is devoted to the proof of the main theorem (the proof is very nice in my opinion).

The talk is based on a recent paper of J. van den Heuvel and S. Thomasse (http://arxiv.org/pdf/0912.2929).

♦ ♦ ♦

Abstrakt:

We present a general result about weighted matroids which has many interesting corollaries. The first corollary is a special case of a conjecture on cyclic orderings of matroids, the second one proves a conjecture of Goncalves and the third one is a generalization of a result of Nash-Williams on disjoint spanning trees in graphs for matroids. Another corollary is the equality of circular and fractional arboricity of matroids.

The talk is divided into two parts. In the first part we introduce matroids and the basic concepts of matroid theory: independence, basis, rank, and duality of matroids. Then we present certain conjectures on cyclic orderings and arboricity of matroids. The second part is devoted to the proof of the main theorem (the proof is very nice in my opinion).

The talk is based on a recent paper of J. van den Heuvel and S. Thomasse (http://arxiv.org/pdf/0912.2929).

♦ ♦ ♦

Abstrakt:

*D*digraf. Označme

*γ(D)*jeho dominančné číslo a označme symbolom

*D*digraf, ktorý vznikne z

^{-}*D*prevrátením orientácie všetkych šípov. V prednáške ukážeme, že pre každé

*d ≥ 3*a

*k ≥ 1*existuje jednoduchý silne suvislý

*d*-regulárny digraf

*D*taký, že

_{d,k}*γ(D*. Ináč povedané, rozdiel dominančného čísla digrafu a jeho reverzu môže byť ľubovoľne veľký dokonca aj v triede silne súvislých regulárnych digrafov. Podobný výsledok sme dosiahli pre totálne dominančné číslo, avšak tu potrebujeme aby stupeň spĺňal

_{d,k})-γ(D^{-}_{d,k})=k*d ≥ 4*. Digraf

*D*sa zostrojil pomocou zdvihu malého orientovaného grafu (so slučkami a násobnými šípmi) najprv v grupe

_{d,k}*Z*a potom v

_{3}*Z*.

_{2k}♦ ♦ ♦

*"The Weak and Strong Perfect Graph Conjecture II"*

Abstrakt:

A graph G is perfect if the chromatic number of any induced subgraph H of G is equal to the size of a largest clique in H. A graph G is a Berge graph if it does not contain an odd cycle or a complement of an odd cycle as an induced subgraph. The famous Strong perfect graph conjecture (SPGC) states that a graph is perfect if and only if it is a Berge graph. The Weak perfect graph conjecture (WPGC) states that the complement of a perfect graph is also perfect. We continue our talk from 4. 3. 20101 by sketching the proof of the SPGT.

Our talk is based on the papers

F. Roussel, I. Rusu, H. Thullier: "The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution" doi: 10.1016/j.disc.2009.05.024

and

P. Seymour: "How the proof of the strong perfect graph conjecture was found" http://www.math.princeton.edu/~pds/papers/howtheperfect/howtheperfect.ps.

♦ ♦ ♦

Abstrakt:

A graph G is perfect if the chromatic number of any induced subgraph H of G is equal to the size of a largest clique in H. A graph G is a Berge graph if it does not contain an odd cycle or a complement of an odd cycle as an induced subgraph. The famous Strong perfect graph conjecture (SPGC) states that a graph is perfect if and only if it is a Berge graph. The Weak perfect graph conjecture (WPGC) states that the complement of a perfect graph is also perfect.

Our talk is devoted to the methods that lead to the proofs of WPGC and SPGC. In the first part (4. 3. 2010) we introduce perfect graphs and describe the so-called primitive classes of perfect graphs. The perfectness of a graph can be stated in terms of linear programming; using this approach we sketch one of the first proofs of the WPGC following Fulkerson and Lovasz. We will continue 11. 3. 2010 by sketching the proof of the SPGT.

Our talk is based on the papers

F. Roussel, I. Rusu, H. Thullier: "The Strong Perfect Graph Conjecture: 40 years of attempts, and its resolution" doi: 10.1016/j.disc.2009.05.024

and

P. Seymour: "How the proof of the strong perfect graph conjecture was found" http://www.math.princeton.edu/~pds/papers/howtheperfect/howtheperfect.ps.

*Abstrakty starších prednášok budú doplňované priebežne.*