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
How to Cite
Bonamy, M., Charbit, P., Defrain, O., Joret, G., Lagoutte, A., Limouzy, V., Pastor, L., & Sereni, J.-S. (2020). Revisiting a Theorem by Folkman on Graph Colouring. The Electronic Journal of Combinatorics, 27(1), P1.56. https://doi.org/10.37236/8899
Issue
Volume 27, Issue 1 (2020)
Article Number
P1.56