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
DOI: https://doi.org/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 $2$ plus the maximum over all subgraphs of the difference between the number of vertices and twice the independence number.

Published
2020-03-20
Issue
Volume 27, Issue 1 (2020)
Article Number
P1.56