Graph coloring and reverse mathematics

被引：0

作者：

Schmerl, JH ^{[1
]}

机构：

[1] Univ Connecticut, Dept Math, Storrs, CT 06269 USA

来源：

MATHEMATICAL LOGIC QUARTERLY | 2000年 / 46卷 / 04期

关键词：

reverse mathematics; graph coloring; recursive inseparability;

D O I：

10.1002/1521-3870(200010)46:4<543::AID-MALQ543>3.0.CO;2-E

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Improving a theorem of Gasarch and Hirst, we prove that if 2 less than or equal to k less than or equal to m less than or equal to omega, then the following is equivalent to WKL0 over RCA(0): Every locally k-colorable graph is m-colorable.

引用

页码：543 / 548

页数：6