Abstracts



Choice number of almost planar graphs

A vertex colouring of a graph G is a mapping of colours to the vertices of G such that adjacent vertices get different colours. Given lists L(v) associated with each vertex v in V(G) a list colouring of G is a vertex colouring such that each vertex v recieves a colour from L(v). If such a colouring exists, we say that G is colourable by L. The choice number ch(G) is the smallest integer k such that, for any L with |L(v)| >= k for all v in V(G), G is colourable by L. The crossing number is the smallest integer k such that G can be drawn in the plane with k crossing edges. If cr(G) = 0, then we say that G is planar. Solving a conjecture of P. Erdös open for more than 20 years, Thomassen showed that if G is planar, then ch(G) <= 5. We improve Thomassen's result by showing that if G has an edge e such that G-e is planar, then ch(G) <= 5. We also show that if cr(G) <= 2, then ch(G) <=5. The proofs are constructive and give rise to algorithms for list colouring such graphs.


Reconstructing ancestral histories: some combinatorial problems

I will discuss the problem of constructing the ancestral history (pedigree) of a population from observations on living individuals in the population. I will give a background of some probabilistic and combinatorial results in phylogenetics that motivate this work. In the rest of the talk I will concentrate on a hypergraph reconstruction problem, solving which will significantly improve the results on the problem of reconstructing ancestral histories.


A proof of a conjecture of Ohba

A list assignment for a graph G is a list of colours for every vertex. An acceptable colouring for this assignment is a choice of a colour from its list for each vertex such that no edge is monochromatic. The list chromatic number of G is the minimum k such that if each list has size at least k then there is an acceptable colouring. Clearly the list chromatic number is at least the chromatic number. Many researchers, some French others Brazilian, have focussed on proving that the list chromatic number of a graph is exactly its chromatic number for certain classes of graphs. We prove a conjecture of Ohba that this is the case if the chromatic number is at least half of the number of vertices. This is joint work with Jon Noel and Hehui Wu.


To Satisfy Impatient Web Surfers is Hard

Prefetching is a basic mechanism for faster data access and efficient computing. An important issue in prefetching is the tradeoff between the amount of network’s resources wasted by the prefetching and the gain of time. For instance, in the Web, browsers may download documents in advance while a Web surfer is surfing on the Web. Since the Web surfer follows the hyperlinks in an unpredictable way, the choice of the Web pages to be prefetched must be computed online. The question is then to determine the minimum amount of resources used by prefetching that ensures that all documents accessed by the Web surfer have previously been loaded in the cache. We model this problem as a two-players game similar to Cops and Robber Games in graphs. The first player, a fugitive, starts on a marked vertex of a (di)graph G. The second player, an observer, marks k ≥ 1 vertices, then the fugitive moves along one edge/arc of G to a new vertex, then the observer marks k vertices, etc. The observer wins if he prevents the fugitive to reach an unmarked vertex. The fugitive wins otherwise, i.e., if she succeed to enter an unmarked vertex. The surveillance number of a (di)graph is the minimum k ≥ 1 allowing the observer to win against any strategy of the fugitive. We study the computational complexity of the game. We show that deciding whether the surveillance number of a chordal graph equals 2 is NP-hard. Deciding if the surveillance number of a DAG equals 4 is PSPACE-complete. Moreover, computing the surveillance number is NP- hard in split graphs. On the other hand, we provide polynomial time algorithms computing surveillance numbers of trees and interval graphs. Moreover, in the case of trees, we establish a combinatorial characterization, related to isoperimetry, of the surveillance number.