Revisiting a theorem by Folkman on graph colouring
arXiv:1907.11429 · doi:10.37236/8899
Abstract
We give a short proof of the following theorem due to Jon H. Folkman (1969): The chromatic number of any graph is at most plus the maximum over all subgraphs of the difference between half the number of vertices and the independence number.
v2: revised following referees' comments