Revisiting a theorem by Folkman on graph colouring (Q2309226)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Revisiting a theorem by Folkman on graph colouring |
scientific article |
Statements
Revisiting a theorem by Folkman on graph colouring (English)
0 references
30 March 2020
0 references
Summary: We give a short proof of the following theorem due to \textit{J. H. Folkman} [in: Combinatorial theory and its applications. Vols. I--III. Amsterdam-London: North Holland Publishing Company. 437--457 (1970; Zbl 0209.55003)]: 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.
0 references
0 references
