Revisiting a Theorem by Folkman on Graph Colouring
Marthe Bonamy, Pierre Charbit, Oscar Defrain, Gwenaël Joret, Aurélie Lagoutte, Vincent Limouzy, Lucas Pastor, Jean-Sébastien Sereni · The Electronic Journal of Combinatorics · 2020
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most $2$ plus the maximum over all subgraphs of the difference between the number of vertices and twice the independence number.