BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Tutorial on defective and clustered graph colouring Wood, David


Consider the following two ways to colour a graph where the requirement that adjacent vertices get distinct colours is relaxed. A colouring has DEFECT $d$ if each monochromatic component has maximum degree at most $d$. A colouring has CLUSTERING $c$ if each monochromatic component has at most $c$ vertices. This talk surveys recent progress on these types of colourings for the following graph classes: planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdiere parameter, graphs with given thickness, graphs with given book-thickness, graphs excluding $K_t$ as a minor, graphs excluding $K_{s,t}$ as a minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open problems are discussed. This is joint work with Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060), Bojan Mohar and Bruce Reed (arXiv:1612.05674), Jan van den Heuvel (arXiv:1704.06536), and Sergey Norin, Alex Scott and Paul Seymour (arXiv:1708.02370).

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International