Loading [MathJax]/extensions/tex2jax.js
Lin­ear Colour­ing, Cen­tered Colour­ing, Treedepth, Treewidth, and Grids
Pat Morin
Car­leton Uni­ver­sity

In this talk I will give an overview of re­cent re­sults re­lat­ing the lin­ear chro­matic num­ber of a graph to its treedepth (aka, cen­tered chro­matic num­ber) and dis­cuss a bold con­jec­ture of Kun, O'Brien, Pilipczuk, and Sul­li­van about a con­di­tion-free re­la­tion­ship be­tween the lin­ear and cen­tered chro­matic num­bers of a graph. This will in­clude re­cent joint work with Bose, Du­j­mović, Houdrouge, and Javarsineh that sharp­ens the upper bound on cen­tered chro­matic num­ber as a func­tion of lin­ear chro­matic num­ber and pro­vides fur­ther ev­i­dence in sup­port of the con­jec­ture.