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 Kt as a minor, graphs excluding Ks,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 |