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

Formale Metadaten

Titel
Tutorial on defective and clustered graph colouring
Serientitel
Anzahl der Teile
24
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.
Schlagwörter