Linear Colouring, Centered Colouring, Treedepth, Treewidth, and Grids
Pat Morin
Carleton University
In this talk I will give an overview of recent results relating the linear chromatic number of a graph to its treedepth (aka, centered chromatic number) and discuss a bold conjecture of Kun, O'Brien, Pilipczuk, and Sullivan about a condition-free relationship between the linear and centered chromatic numbers of a graph. This will include recent joint work with Bose, Dujmović, Houdrouge, and Javarsineh that sharpens the upper bound on centered chromatic number as a function of linear chromatic number and provides further evidence in support of the conjecture.