We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Tutorial on defective and clustered graph colouring

Formal Metadata

Title
Tutorial on defective and clustered graph colouring
Title of Series
Number of Parts
24
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
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.
Keywords