Maximum number of colourings: 4-chromatic graphs
| Autor: | Fiachra Knox, Bojan Mohar |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Conjecture
010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Chromatic scale 0101 mathematics Connectivity Mathematics |
| Zdroj: | Journal of Combinatorial Theory, Series B. 144:95-118 |
| ISSN: | 0095-8956 |
| DOI: | 10.1016/j.jctb.2020.01.002 |
| Popis: | It is proved that every connected graph G on n vertices with χ ( G ) ≥ 4 has at most k ( k − 1 ) n − 3 ( k − 2 ) ( k − 3 ) k-colourings for every k ≥ 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 [29] . Proof methods may be of independent interest. In particular, one of our auxiliary results about list-chromatic polynomials solves a generalized version of a recent conjecture of Brown, Erey, and Li. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect