Defective and clustered graph colouring

Research output: Contribution to journalArticleResearchpeer-review

9 Citations (Scopus)

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 languageEnglish
Article numberDS23
Number of pages71
JournalThe Electronic Journal of Combinatorics
Volume1
Issue numberDynamicSurveys
Publication statusPublished - 13 Apr 2018

Cite this