Defective and clustered graph colouring
Summary: 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 \textit{defect} \(d\) if each monochromatic component has maximum degree at most \(d\). A colouring has \textit{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.
- Path choosability of planar graphs
- On generalized choice and coloring numbers
- Isomorphic bisections of cubic graphs
- On the \(k\)-component independence number of a tree
- Vizing's and Shannon's theorems for defective edge colouring
- Distance \(r\)-domination number and \(r\)-independence complexes of graphs
- On 2-defective DP-colorings of sparse graphs
- Defective DP-colorings of sparse multigraphs
- Improper interval edge colorings of graphs
- Defective DP-colorings of sparse simple graphs
- Clustered colouring in minor-closed classes
- Defective colouring of graphs excluding a subgraph or minor
- Clustered variants of Hajós' conjecture
- Higher independence complexes of graphs and their homotopy types
- Improper colouring of graphs with no odd clique minor
- Defective and clustered choosability of sparse graphs
- Clustered colouring of graph classes with bounded treedepth or pathwidth
- Improved bound for improper colourings of graphs with no odd clique minor
- Clustered 3-colouring graphs of bounded degree
- Polynomial bounds for chromatic number. III. Excluding a double star
- Decomposing planar graphs into graphs with degree restrictions
- Defective coloring of hypergraphs
- Sparse critical graphs for defective DP-colorings
- Defective coloring is perfect for minors
- Product structure extension of the Alon-Seymour-Thomas theorem
- Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
- Clustered coloring of graphs with bounded layered treewidth and bounded degree
- Weak diameter coloring of graphs on surfaces
- Colouring strong products
- Product structure of graph classes with bounded treewidth
- Cops and robbers on multi-layer graphs
- Defective coloring of blowups
- Extremal density for subdivisions with length or sparsity constraints
- A reduction of the ``cycles plus \(K_4\)'s problem
- Computational complexity of covering multigraphs with semi-edges: small cases
- Sparse critical graphs for defective (1, 3)-coloring
- Product structure of graph classes with strongly sublinear separators
- Clustered colouring of graph products
- Weak diameter choosability of graphs with an excluded minor
- Clustered coloring of (path + 2K₁)-free graphs on surfaces
- The interval coloring impropriety of planar graphs
- Stanley-Reisner ideals of higher independence complexes of chordal graphs
- Defective and clustered colouring of graphs with given girth
- Clustered coloring of graphs excluding a subgraph and a minor
- Chessboard and level sets of continuous functions
This page was built for publication: Defective and clustered graph colouring
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1751289)
