ProgramThursday, November 18, 2010The workshop will start at 13:45.
Friday, November 19, 2010
Saturday, November 20, 2010
AbstractsJorgen BangJensen  On the problem of finding disjoint cycles and dicycles in a digraphWe consider the following problem: Given a digraph D, decide if there is a cycle B in D and a cycle C in its underlying undirected graph UG(D) such that V(B) ∩ V(C) = ∅. Whereas the problem is NPcomplete if, as additional part of the input, a vertex x is prescribed to be contained in C, we give an overview of our recent proof that one can decide the existence of B,C in polynomial time under the (mild) additional assumption that D is strongly connected. Our methods actually find B,C in polynomial time if they exist. The behaviour of the problem as well as our solution depend on the cycle transversal number τ(D) of D, i.e. the smallest cardinality of a set T of vertices in D such that DT is acyclic: If τ(D)≥3 then we employ McCuaig's framework on intercyclic digraphs to (always) find these cycles. If τ(D)=2 then we can characterize the digraphs for which the answer is "yes" by using topological methods relying on Thomassen's theorem on 2linkages in acyclic digraphs. For the case τ(D)≤1 we provide an algorithm independent from any earlier work. JeanClaude Bermond  Directed acyclic graphs with the unique dipath propertyLet P be a family of dipaths of a DAG (Directed Acyclic Graph) G. The load of an arc is the number of dipaths containing this arc. Let π(G,P) be the maximum of the load of all the arcs and let w(G,P) be the minimum number of wavelengths (colors) needed to color the family of dipaths P in such a way that two dipaths with the same wavelength are arcdisjoint. There exist DAGs such that the ratio between w(G,P) and π(G,P) cannot be bounded. An internal cycle is an oriented cycle such that all the vertices have at least one predecessor and one successor in G (said otherwise every cycle contain neither a source nor a sink of G). We prove that, for any family of dipaths P, w(G, P) = π(G, P) if and only if G is without internal cycle. We also consider a new class of DAGs, which is of interest in itself, those for which there is at most one dipath from a vertex to another. We call these digraphs UPPDAGs. For these UPPDAGs we show that the load is equal to the maximum size of a clique of the conflict graph. We prove that the ratio between w(G,P) and π(G,P) cannot be bounded (a result conjectured in an other article). For that we introduce "good labelings" of the conflict graph associated to G and P, namely labelings of the edges such that for any ordered pair of vertices (x, y) there do not exist two paths from x to y with increasing labels. Adrian Bondy  Induced Decompositions of GraphsWe describe a new type of graph decomposition and present some basic results about it. This is joint work with Jayme Szwarcfiter. Louis Esperet  Perfect matching in cubic graphsWe prove that cubic bridgeless graph have exponentially many perfect matchings. This was conjectured in the mid70's by Lovasz and Plummer. (joint work with F. Kardos, A. King, D. Kral, and S. Norin) Guillaume Fertin  On some Graph Coloring ProblemsAndré Raspaud was the man who made me discover the delights of graph coloring. Since then, and though this is not my main line of research today, I sometimes like to play around with (and, if possible, contribute to) some graph coloring and graph labeling problems. In this talk, I will survey some results about graph coloring, with a focus on acyclic coloring. Time permits, I will also mention some results obtained with Stéphane Vialette (U. ParisEst) on the socalled "Slabeling problem". Daniel Gonçalves  SDDelaunay Triangulations and the DuschnikMiller Dimension of Simplicial ComplexesIn 1989, W. Schnyder gave a new charaterisation of planar graphs by means of the DuschnikMiller dimension of their inclusion poset : A graph is planar if and only if its inclusion poset has DuschnikMiller dimension at most 3. In 1999, P. Ossona de Mendez showed that simplicial complexes whose inclusion posets have DuschnikMiller dimension bounded by d are linearly embeddable in R^{d1}. Unfortunately the converse is only true for d ≤ 3. In this work we give a geometric characterization of simplicial complexes whose inclusion posets have DuschnikMiller dimension d as special Delaunay triangulations of points in R^{d1}. This generalizes a recent work of Bonichon et al for the case d=3. Gena Hahn  Vertex transitive copwin graphs...and moreMany years ago, Nowakowski and Winkler, and, independently, Quilliot, characterized the graphs on which one cop can catch a single robber in the game where the cop begins and the two players alternately move along the edges of a reflexive graph. It is easy to see that there are no regular copwin graphs that are not complete... if we demand that they be finite. In this talk we describe what we know for infinite graphs; in particular, we say why the finitegraph characterization does not work and we show that for every infinite cardinal there are as many nonisomorphic vertextransitive copwin graphs as possible. This is work with Bonato, Laviolette, Sauer, Tardif and Woodrow over the years. Pavol Hell  List homomorphisms and variants of interval graphsI will describe a new combinatorial classification of the complexity of list homomorphisms. Previously, only an algebraic classification (due to A.A. Bulatov) was known for digraphs, although in the special case of graphs there existed more combinatorial classifications. The classification for graphs is closely related to the class of interval graphs, and these new generalizations suggest interesting new classes of digraphs, with many qualities resembling interval graphs. Alexandr Kostochka  Edge and vertexpartitions of graphs with bounded maximum average degreeA convenient measure of sparseness of a graph G is the maximum average degree of G, mad(G):=max {2E(H)/V(H): H ⊆ G}. For example, mad(G)<2g/(g2) for every planar graph with girth g. Another measure of sparseness is the maximum degree, Δ(G), of G. Say that G is dbounded, if Δ(G)≤d. We prove that every graph G with mad(G)<44/(d+2) decomposes into a forest and a dbounded graph. The result is sharp, since for every d≥1, there are graphs G_d with mad(G_d)=44/(d+2) that do not have such decomposition. It implies several recent results on planar graphs with given girth. We also prove that every graph G with mad(G)≤12/5 contains an independent set I such that GI is 1bounded. This bound is sharp. Some results related to the two just described will be discussed. The talk is based on results joint with O. Borodin, S.J. Kim, D. B. West, H. Wu, and X. Zhu. Jarik Nesetril  OrientationsThe relationship between (undirected) graphs and their orientations is an example of perhaps the simplest expansion (lift) of finite structures. It leads to several interesting questions some of which will be surveyed in this talk. Particularly I want to concentrate on some topics related to our joint work with André. Ingo Schiermeyer  Progress on rainbow connectionAn edgecoloured graph G is called rainbow connected if any two vertices are connected by a path whose edges have distinct colours. This concept of rainbow connection in graphs was introduced by Chartrand et al.. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colours that are needed in order to make G rainbow connected. In this talk we will present several lower and upper bounds for rc(G). We will discuss rc(G) for graphs with given minimum degree. Finally, we will present some recent ErdösGallai type results for rc(G). Martin Skoviera  Local 3edgecolourings of cubic graphsWe develop the idea of a local 3edgecolouring of a cubic graph, a generalisation of the usual 3edgecolouring which uses an unlimited number of colours subject to the condition that, whenever two colours meet at a vertex, the third colour will always be the same. We describe local 3edgecolourings in terms of colourings by points of a partial Steiner triple system such that the colours around each vertex form a block of the system. An important place in our investigation is held by colourings that use two smallest nontrivial Steiner triple systems, the Fano plane PG(2,2) and the affine plane AG(2,3). We also discuss the relationship of local 3edgecolourings to several old and new conjectures concerning cubic graphs, including the Cycle Double Cover Conjecture, the Fulkerson conjecture, and the conjecture of Fan and Raspaud. Bjarne Toft  Reverse hex  New proofs and new results.Reverse Hex, also known as Rex or Misère Hex, is the variant of Hex in which the player who connects his/her two sides loses. After a brief survey of Reverse Hex, its history and all previous results on Reverse Hex, we update proofs and results for general nxnboards. We give new simple proofs and strengthened versions of Lagarias and Sleator's theorem (each player can prolong the game until the board is full, so the first/second player can always win if n is even/odd), and of Evans'theorem (for even n, opening in the acute corner is a winning move). Also, for even n at least 4, we find another firstplayer winning opening (adjacent to the acute corner on the first player's side). Moreover, for n odd at least 3 and for each firstplayer opening, we find a secondplayer winning reply. Finally, in response to comments by Martin Gardener, we give simple winning strategies for boardsize up to 5x5. This is joint work with Ryan Hayward, University of Alberta. Xuding Zhu  Chromatic Ramsey number of graphs and fractional chromatic number of product graphsWe write F→(G,G) if for any 2edge colouring of F, there is a monochromatic copy of G. The chromatic Ramsey number R_{χ}(G) of G is defined as the minimum chromatic number of F for which F→(G,G). It is an easy observation that if χ(G)=n, then R_{χ}(G) ≥ (n1)^{2}+1. In 1976, BurrErdösLovasz conjectured that for any positive integer n, there exists an nchromatic graph G with R_{χ}(G)=(n1)^{2}+1. This conjecture was verified for n ≤ 5 before. Recently, the author confirmed the whole conjecture. The proof of this conjecture involves an approach related to another wellknown long standing conjecture: Hedetniemi's conjecture, which states that the categorical product of two nchromatic graphs has chromatic number n. I proved the fractional version of this conjecture: For two graphs with fractional chromatic number at least r, their categorical product has fractional chromatic number at least r. It is by using this result that we settled BurrErdösLovasz conjecture.

Sponsors :
