The chromatic number of dense random graphs
The chromatic number χ(G) of a graph G is defined as the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. The chromatic number of the dense random graph G ∼ G(n, p) where p ∈ (0, 1) is constant has been intensively studied since the 1970...
| Main Author: | |
|---|---|
| Format: | Journal article |
| Published: |
Wiley
2018
|
| _version_ | 1797078072507236352 |
|---|---|
| author | Heckel, A |
| author_facet | Heckel, A |
| author_sort | Heckel, A |
| collection | OXFORD |
| description | The chromatic number χ(G) of a graph G is defined as the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. The chromatic number of the dense random graph G ∼ G(n, p) where p ∈ (0, 1) is constant has been intensively studied since the 1970s, and a landmark result by Bollob´as in 1987 first established the asymptotic value of χ(G) [4]. Despite several improvements of this result, the exact value of χ(G) remains open. In this paper, new upper and lower bounds for χ(G) are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the colouring rate n/χ(G) of G ∼ G(n, p) to an explicit interval of length o(1), answering a question of Kang and McDiarmid [14]. |
| first_indexed | 2024-03-07T00:27:13Z |
| format | Journal article |
| id | oxford-uuid:7e8e37b8-1f7b-4812-acbf-bccf0c0b1942 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:27:13Z |
| publishDate | 2018 |
| publisher | Wiley |
| record_format | dspace |
| spelling | oxford-uuid:7e8e37b8-1f7b-4812-acbf-bccf0c0b19422022-03-26T21:10:46ZThe chromatic number of dense random graphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7e8e37b8-1f7b-4812-acbf-bccf0c0b1942Symplectic Elements at OxfordWiley2018Heckel, AThe chromatic number χ(G) of a graph G is defined as the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. The chromatic number of the dense random graph G ∼ G(n, p) where p ∈ (0, 1) is constant has been intensively studied since the 1970s, and a landmark result by Bollob´as in 1987 first established the asymptotic value of χ(G) [4]. Despite several improvements of this result, the exact value of χ(G) remains open. In this paper, new upper and lower bounds for χ(G) are established. These bounds are the first ones that match each other up to a term of size o(1) in the denominator: they narrow down the colouring rate n/χ(G) of G ∼ G(n, p) to an explicit interval of length o(1), answering a question of Kang and McDiarmid [14]. |
| spellingShingle | Heckel, A The chromatic number of dense random graphs |
| title | The chromatic number of dense random graphs |
| title_full | The chromatic number of dense random graphs |
| title_fullStr | The chromatic number of dense random graphs |
| title_full_unstemmed | The chromatic number of dense random graphs |
| title_short | The chromatic number of dense random graphs |
| title_sort | chromatic number of dense random graphs |
| work_keys_str_mv | AT heckela thechromaticnumberofdenserandomgraphs AT heckela chromaticnumberofdenserandomgraphs |