Accepted author manuscript, 399 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - When removing an independent set is optimal for reducing the chromatic number
AU - Cambie, Stijn
AU - Haslegrave, John
AU - Kang, Ross
PY - 2024/1/31
Y1 - 2024/1/31
N2 - 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.
AB - 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.
U2 - 10.1016/j.ejc.2023.103781
DO - 10.1016/j.ejc.2023.103781
M3 - Journal article
VL - 115
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
SN - 0195-6698
M1 - 113781
ER -