- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Tutorial on defective and clustered graph colouring
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Tutorial on defective and clustered graph colouring Wood, David
Description
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. This is joint work with Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060), Bojan Mohar and Bruce Reed (arXiv:1612.05674), Jan van den Heuvel (arXiv:1704.06536), and Sergey Norin, Alex Scott and Paul Seymour (arXiv:1708.02370).
Item Metadata
| Title |
Tutorial on defective and clustered graph colouring
|
| Creator | |
| Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
| Date Issued |
2017-08-21T09:01
|
| Description |
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. This is joint work with
Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060), Bojan
Mohar and Bruce Reed (arXiv:1612.05674), Jan van den Heuvel
(arXiv:1704.06536), and Sergey Norin, Alex Scott and Paul Seymour
(arXiv:1708.02370).
|
| Extent |
60 minutes
|
| Subject | |
| Type | |
| File Format |
video/mp4
|
| Language |
eng
|
| Notes |
Author affiliation: Monash University
|
| Series | |
| Date Available |
2018-04-09
|
| Provider |
Vancouver : University of British Columbia Library
|
| Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
| DOI |
10.14288/1.0365253
|
| URI | |
| Affiliation | |
| Peer Review Status |
Unreviewed
|
| Scholarly Level |
Faculty
|
| Rights URI | |
| Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International