ProgramDetailed programAbstracts of plenary talksInduced cycles and coloring  Maria Chudnovsky The Strong Perfect Graph Theorem states that a graph and all its induced subgraphs have equal clique number and the chromatic number if and only if the graph contains no induced odd cycle of length at least five, and no complement of one. But what happens if only some induced cycles (and no complements)are excluded? Gyarfas made a number of conjectures on this topic, asserting that in many cases the chromatic number is bounded by a function of the clique number. In this talk we discuss recent progress on some of these conjectures. This is joint work with Alex Scott and Paul Seymour. The Firefighter Problem: A survey of directions, results, and problems  Gary MacGillivray Imagine that a fire breaks out at one or more vertices of a graph, and at each time interval spreads to all neighbouring vertices that have not been protected so far. This is the general setup for the Firefighter Problem, which has attracted considerable attention since being introduced by Hartnell in 1995. We shall survey various directions that have been pursued, and results that have been obtained. Examples include whether the fire can be contained on infinite grids, algorithms, and complexity theorems. Open problems and possible directions for future research will also be discussed. Discrete isoperimetric problems  Oriol Serra The isoperimetric problem for graphs asks for the cardinality of the minimum (edge or vertex) boundary among sets of vertices with given cardinality. An ordering of the vertex set of a graph is isoperimetric if its initial segments are optimal sets for the isoperimetric problem. The classical theorems of KruskalKatona and Harper show that the ncube admits an isoperimetric order. In the talk we will discuss a localglobal principle which extends analogous results for certain classes of cartesian products of graphs and provides simple proofs for several known results. Algorithmic aspects concerning the existence of a set of nested solutions for graphs with bounded treewidth will be also addressed. List colorings of planar graphs  Margit Voigt Local irregularity  Mariusz Wozniak A locally irregular graph is a graph whose adjacent vertices have distinct degrees. We say that a graph G can be decomposed into k locally irregular subgraphs if its edge set may be partitioned into k subsets each of which induces a locally irregular subgraph in G. We characterize all connected graphs which cannot be decomposed into locally irregular subgraphs. These are all of odd size and include paths, cycles and a special class of graphs of maximum degree 3. Moreover we conjecture that apart from these exceptions all other connected graphs can be decomposed into three locally irregular subgraphs. We also investigate a total version of this problem, where in some sense also the vertices are being prescribed to particular subgraphs of a decomposition. The both concepts are closely related to the known 123 Conjecture and 12 Conjecture, as well as to other similar problems concerning edge and arc colorings of graphs and digraphs, respectively. Online list colouring of graphs  Xuding Zhu The online colouring game on a family F of graphs is played by two players: Presenter and Algorithm. In each round, Presenter add one new vertex v to the existing graph, including all edges connecting v to earlier vertices. The resulting graph must be in the family F. Algorithm colours v with a colour not used by any of its existing neighbours. The nround) online chromatic number of F is the least number of colours sufficient for Algorithm to play the game for nrounds. Equivalently, it is the maximum number of colours Presenter can force the Algorithm to use in nrounds. It was proved by Lovasz, Saks and Trotter that the (nround) online chromatic number of bipartite graphs is at most 2 log n. A recent result of Bianchi shows that it is at least 1.13746 log n  0.49887. We improve this lower bound to 2 log n  10, which differs from the upper bound by an additive constant. It was proved by Kierstead that graphs of odd girth 7 has (nround) online chromatic number O(n^{1/2}), and we give a lower bound and prove that this family of graphs has (nround) online chromatic number Omega(n/((log n)^{1/3})). This is a joint work with Grzegorz Gutowski, Jakub Kozik and Piotr Micek. 
Sponsors:
