[DMO] Jan van den Heuvel : Partial Colourings

03 november 2023 14:00 t/m 15:00 - Locatie: Lecture Hall G, 36.HB.00.230 | Zet in mijn agenda

Suppose you have a graph G for which you know the vertices can be properly coloured with t colours, but you only have s < t colours available. Then it is an easy observation that you can still properly colour at least a fraction s/t of the vertices of G. (More formally: there exists an induced subgraph H of G such that H is s-colourable and |V(H)| ≥ s/t|V(G)|.) But the situation is less clear when we look at other types of colourings, such as list-colourings, fractional colourings, multi-colourings, etc.
In this talk we mostly focus on multi-colouring. An (n,k)-colouring of a graph is an assignment of a k-subset of {1, 2, . . . , n} to each vertex such that adjacent vertices receive disjoint subsets. And the question we are looking at is: given a graph G that is (n,k)-colourable, how large can we guarantee an (n',k')-colourable induced subgraph to be (for some given (n',k'))? Answering that question leads to having to look at combinatorial objects such as set systems and Kneser graphs, and is connected to several open problems in those areas.
This is joint work with Xinyi Xu.