Geodesic
Revisiting a theorem by Folkman on graph colouring
The electronic journal of combinatorics, Tome 27 (2020) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/8899
Classification : 05C15

Marthe Bonamy    ; Pierre Charbit    ; Oscar Defrain    ; Gwenaël Joret  1   ; Aurélie Lagoutte    ; Vincent Limouzy    ; Lucas Pastor    ; Jean-Sébastien Sereni  2

1 Université Libre de Bruxelles
2 C.N.R.S. 
@article{10_37236_8899,
     author = {Marthe Bonamy and Pierre Charbit and Oscar Defrain and Gwena\"el Joret and Aur\'elie Lagoutte and Vincent Limouzy and Lucas Pastor and Jean-S\'ebastien Sereni},
     title = {Revisiting a theorem by {Folkman} on graph colouring},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {1},
     doi = {10.37236/8899},
     zbl = {1435.05071},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/8899/}
}
TY  - JOUR
AU  - Marthe Bonamy
AU  - Pierre Charbit
AU  - Oscar Defrain
AU  - Gwenaël Joret
AU  - Aurélie Lagoutte
AU  - Vincent Limouzy
AU  - Lucas Pastor
AU  - Jean-Sébastien Sereni
TI  - Revisiting a theorem by Folkman on graph colouring
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/8899/
DO  - 10.37236/8899
ID  - 10_37236_8899
ER  - 
%0 Journal Article
%A Marthe Bonamy
%A Pierre Charbit
%A Oscar Defrain
%A Gwenaël Joret
%A Aurélie Lagoutte
%A Vincent Limouzy
%A Lucas Pastor
%A Jean-Sébastien Sereni
%T Revisiting a theorem by Folkman on graph colouring
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/8899/
%R 10.37236/8899
%F 10_37236_8899
Marthe Bonamy; Pierre Charbit; Oscar Defrain; Gwenaël Joret; Aurélie Lagoutte; Vincent Limouzy; Lucas Pastor; Jean-Sébastien Sereni. Revisiting a theorem by Folkman on graph colouring. The electronic journal of combinatorics, Tome 27 (2020) no. 1. doi: 10.37236/8899

Cité par Sources :