- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Maximum number of colourings and Tomescu's conjecture
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Maximum number of colourings and Tomescu's conjecture Mohar, Bojan
Description
It is proved that every connected graph $G$ on $n$ vertices with $\chi(G) \geq 4$ has at most $k(k-1)^{n-3}(k-2)(k-3)$ $k$-colourings for every $k \geq 4$. Equality holds for some (and then for every) $k$ if and only if the graph is formed from $K_4$ by repeatedly adding leaves. This confirms (a strengthening of) the $4$-chromatic case of a long-standing conjecture of Tomescu [Le nombre des graphes connexes $k$-chromatiques minimaux aux sommets etiquetes, C. R. Acad. Sci. Paris 273 (1971), 1124--1126]. Proof methods may be of independent interest. In particular, one of our auxiliary results about list-chromatic polynomials solves a recent conjecture of Brown, Erey, and Li. (Joint work with Fiachra Knox.)
Item Metadata
Title |
Maximum number of colourings and Tomescu's conjecture
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2017-08-23T11:20
|
Description |
It is proved that every connected graph $G$ on $n$ vertices with $\chi(G)
\geq 4$ has at most $k(k-1)^{n-3}(k-2)(k-3)$ $k$-colourings for every $k
\geq 4$.
Equality holds for some (and then for every) $k$ if and only if the graph is
formed from $K_4$ by repeatedly adding leaves.
This confirms (a strengthening of) the $4$-chromatic case of a long-standing
conjecture of Tomescu [Le nombre des graphes connexes $k$-chromatiques
minimaux aux sommets etiquetes, C. R. Acad. Sci. Paris 273 (1971),
1124--1126]. Proof methods may be of independent interest. In particular,
one of our auxiliary results about list-chromatic polynomials solves a
recent conjecture of Brown, Erey, and Li.
(Joint work with Fiachra Knox.)
|
Extent |
29 minutes
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Simon Fraser University
|
Series | |
Date Available |
2018-04-11
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0365329
|
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