New Perspectives in Colouring and Structure (Online) (20w5143)
The Banff International Research Station will host the "New Perspectives in Colouring and Structure" workshop in Banff from March 15 to March 20, 2020. The study of graph colouring is a central theme in combinatorics. Calculating the chromatic number of a graph is well-known to be NP-hard (indeed it is NP-hard even to approximate the chromatic number), and so it is perhaps not surprising that graph colouring has a rich theory, with many important open problems. The colouring of graphs, and more generally of directed graphs and hypergraphs, also has connections and applications in many other areas, including algorithm design, scheduling and resource allocation, statistical physics, and social choice theory. A common theme in colouring problems is the relationship between chromatic number and graph structure. For instance, one of the oldest problems in graph theory was the celebrated Four Colour Conjecture on colouring planar graphs, which was raised in 1852 and only proved in 1976. A vastly more general conjecture made by Hadwiger in 1943 is still open: if a graph cannot be properly coloured with $k-1$ colours then it must contain the complete graph on $k$ vertices as a minor. In the last few years, there have been some important steps forward on Hadwiger’s Conjecture, and major progress on some of the many other important questions on graph and digraph colouring. This workshop brings together the originators of these new developments, as well as both junior and senior researchers with interests in the field, to explore these new breakthroughs and the new territory they have opened up.
