## Abstract

Consider the following two ways to colour the vertices of 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 paper surveys research on these types of colourings, where the first priority is to minimise the number of colours, with small defect or small clustering as a secondary goal. List colouring variants are also considered. The following graph classes are studied: outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with given maximum degree, graphs with given maximum average degree, graphs excluding a given subgraph, graphs with linear crossing number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, graphs with given circumference, graphs excluding a fixed graph as an immersion, graphs with given thickness, graphs with given stack-or queue-number, 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.

Original language | English |
---|---|

Article number | DS23 |

Number of pages | 71 |

Journal | The Electronic Journal of Combinatorics |

Volume | 1 |

Issue number | DynamicSurveys |

Publication status | Published - 13 Apr 2018 |