Generalised Colouring Numbers of Graphs

Add to your list(s) Download to your calendar using vCal

• Jan van den Heuvel (LSE)
• Thursday 12 January 2017, 15:00-16:00
• LTA Watson.

If you have a question about this talk, please contact Dr Andrew Treglown.

The well-known colouring number of a graph is one more than the smallest k for which there exists an ordering of the vertices in which each vertex has at most k neighbours that come earlier in the ordering. The colouring number is a trivial upper bound for the chromatic number of the graph. But it also contains structural information of the graph, for instance regarding the edge density of any subgraph. When instead of neighbours we count vertices that come earlier in the ordering and can be reached by a path of length at most r, we get the generalised colouring numbers. Depending on conditions for the internal vertices of such paths (disjoint or not; where they can appear in the ordering), we actually can define different types of those generalised colouring numbers. Variants of these generalised colouring numbers were mostly introduced to study specific types of graph colourings. In the last couple of years it has been realised that the generalised colouring numbers are closely related to many structural properties of graphs (such as tree-depth and tree-width). In this talk we give an overview of some aspects of the generalised colouring numbers: mutual relations, relations with structural properties of graphs, relations with specific types of colouring, and bounds for these numbers for for specific classes of graphs (such as planar graphs).

This talk is part of the Combinatorics and Probability Seminar series.

This talk is included in these lists:

• Combinatorics and Probability Seminar
• LTA Watson
• School of Mathematics Events

Note that ex-directory lists are not shown.