Premium
Graph Coloring and Reverse Mathematics
Author(s) -
Schmerl James H.
Publication year - 2000
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/1521-3870(200010)46:4<543::aid-malq543>3.0.co;2-e
Subject(s) - mathematics , graph , graph coloring , combinatorics , discrete mathematics , list coloring , line graph , graph power
Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω , then the following is equivalent to WKL 0 over RCA 0 Every locally k ‐colorable graph is m ‐colorable.