Countable splitting graphs
Volume 212 / 2011
Fundamenta Mathematicae 212 (2011), 217-233
MSC: 03E17, 05C75, 05C99.
DOI: 10.4064/fm212-3-2
Abstract
A graph is called splitting if there is a 0-1 labelling of its vertices such that for every infinite set $C$ of natural numbers there is a sequence of labels along a 1-way infinite path in the graph whose restriction to $C$ is not eventually constant. We characterize the countable splitting graphs as those containing a subgraph of one of three simple types.
