 Research Group Algorithmics and Computational ComplexityTalk 17.03.2017 # The interactive sum choice number of graphs

Kitty Meeks (University of Glasgow)

List colouring is a natural extension of the basic graph colouring problem, in which each vertex v is given a list L_v of permitted colours and we want to find a proper colouring in which every vertex receives a colour from its list.  The choice number of a graph G is the smallest k such that, if every vertex has a list of k permitted colours (chosen by an adversary) we are sure to be able to find a proper list colouring.  However, a graph G may have large choice number due to a small part of G (e.g. a clique) that is "hard" to colour, even if the rest of the graph is "easy" to colour.  The sum choice number of a graph G (introduced by Isaac in 2002) instead captures the "average difficulty" of colouring the graph, as each vertex v is allowed to have a different list length f(v): we still require that, however our adversary assigns colours to the lists, there will always be a proper list colouring of G, but our goal is now to minimise the sum of the list lengths.

We introduce a variant of the sum choice number, called the interactive sum choice number.  Instead of deciding in advance what the list length should be for each vertex, we can now request colours to be added to the vertices' colour-lists one at a time, so that we are able to make use of the information about the colours assigned so far to determine our future choices; the interactive sum choice number is the total number of colours (summed over all vertices) that we have to request, in the worst case, in order to obtain a proper list colouring.  It is clear that the interactive sum choice number cannot exceed the sum choice number; we conjecture that, except in the case of complete graphs, the interactive sum choice is always strictly smaller than the sum choice number.

This conjecture is still wide open, but in this talk I will provide some supporting evidence in its favour: we can show that the conjecture holds in a number of special cases, and indeed that in many of these cases the difference between the two quantities grows as a linear function of the number of vertices.

This is joint work with Marthe Bonamy (Bordeaux).

Date
Speaker
Location
Language
17.03.2017
12:00
Kitty Meeks
TEL 512
English

Back to the research colloquium site.