When removing an independent set is optimal for reducing the chromatic number
| Authors |
|
|---|---|
| Publication date | 01-2024 |
| Journal | European Journal of Combinatorics |
| Article number | 103781 |
| Volume | Issue number | 115 |
| Number of pages | 11 |
| Organisations |
|
| Abstract | How large must the chromatic number of a graph be, in terms of the graph's maximum degree, to ensure that the most efficient way to reduce the chromatic number by removing vertices is to remove an independent set? By a reduction to a powerful, known stability form of Brooks’ theorem, we answer this question precisely, determining the threshold to within two values (and indeed sometimes a unique value) for graphs of sufficiently large maximum degree. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1016/j.ejc.2023.103781 |
| Other links | https://www.scopus.com/pages/publications/85166537506 |
| Downloads |
When removing an independent set is optimal for reducing the chromatic number
(Final published version)
|
| Permalink to this page | |