The t-Improper Chromatic Number of Random Graphs
We consider the t-improper chromatic number of the Erd′s-Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2010
|
| _version_ | 1826301089893318656 |
|---|---|
| author | Kang, R McDiarmid, C |
| author_facet | Kang, R McDiarmid, C |
| author_sort | Kang, R |
| collection | OXFORD |
| description | We consider the t-improper chromatic number of the Erd′s-Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual notion of proper colouring. When the edge probability p is constant, we provide a detailed description of the asymptotic behaviour of χt(Gn,p) over the range of choices for the growth of t = t(n). © 2009 Cambridge University Press. |
| first_indexed | 2024-03-07T05:27:06Z |
| format | Journal article |
| id | oxford-uuid:e0f064a3-6115-4160-bb7a-2811a7aba55d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T05:27:06Z |
| publishDate | 2010 |
| record_format | dspace |
| spelling | oxford-uuid:e0f064a3-6115-4160-bb7a-2811a7aba55d2022-03-27T09:50:53ZThe t-Improper Chromatic Number of Random GraphsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:e0f064a3-6115-4160-bb7a-2811a7aba55dEnglishSymplectic Elements at Oxford2010Kang, RMcDiarmid, CWe consider the t-improper chromatic number of the Erd′s-Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual notion of proper colouring. When the edge probability p is constant, we provide a detailed description of the asymptotic behaviour of χt(Gn,p) over the range of choices for the growth of t = t(n). © 2009 Cambridge University Press. |
| spellingShingle | Kang, R McDiarmid, C The t-Improper Chromatic Number of Random Graphs |
| title | The t-Improper Chromatic Number of Random Graphs |
| title_full | The t-Improper Chromatic Number of Random Graphs |
| title_fullStr | The t-Improper Chromatic Number of Random Graphs |
| title_full_unstemmed | The t-Improper Chromatic Number of Random Graphs |
| title_short | The t-Improper Chromatic Number of Random Graphs |
| title_sort | t improper chromatic number of random graphs |
| work_keys_str_mv | AT kangr thetimproperchromaticnumberofrandomgraphs AT mcdiarmidc thetimproperchromaticnumberofrandomgraphs AT kangr timproperchromaticnumberofrandomgraphs AT mcdiarmidc timproperchromaticnumberofrandomgraphs |